COMMENT ⊗   VALID 00021 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input acphdr % Answer pages (double-check position of figures)
C00004 00003	% Page 516
C00024 00004	% Vicinity of page 519
C00037 00005	% Vicinity of page 522
C00054 00006	% Vicinity of page 525
C00075 00007	% Vicinity of page 528
C00096 00008	% Vicinity of page 531
C00109 00009	% Vicinity of page 534
C00123 00010	% Vicinity of page 537
C00143 00011	% Vicinity of page 540
C00157 00012	% Vicinity of page 543
C00168 00013	% Vicinity of page 545
C00191 00014	% Vicinity of page 548
C00204 00015	% Vicinity of page 551
C00215 00016	% Vicinity of page 553
C00232 00017	% Vicinity of page 555
C00239 00018	% Vicinity of page 557
C00250 00019	% Vicinity of page 559
C00261 00020	% Vicinity of page 560
C00264 00021	\end % be sure this comes at an opportune time!
C00268 ENDMK
C⊗;
\input acphdr % Answer pages (double-check position of figures)
\open0=v2ans1.inx
\chpar19←1 % this will prepare a ".JST" file containing justification statistics
\runninglefthead{ANSWERS TO EXERCISES}
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{ANSWER PAGES for THE ART OF COMPUTER PROGRAMMING}
\ctrline{(Volume 2)}
\ctrline{(first half of the answers)}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\eject
\setcount0 516
% Page 516
% folio 649 galley 1 	*
\titlepage
\runninglefthead{ANSWERS TO EXERCISES}
\corners
\vskip 1in plus 30pt minus 10pt
\rjustline{\:;ANSWERS TO EXERCISES}
\vskip 1cm plus 30pt minus 10pt
\quoteformat{This branch of mathematics is the only one, I believe,\cr
in which good writers frequently get results entirely erroneous.\cr
. . . It may be doubted if there is a single\cr
extensive treatise on probabilities in existence\cr
which does not contain solutions absolutely indefensible.\cr}
\author{C. S. \α{PEIRCE,} in {\sl Popular Science Monthly} (1878)}
\vskip 1cm plus 30pt minus 10pt
\sectionskip\exbegin{NOTES ON THE EXERCISES}
\ansno 1. An average problem for a mathematically inclined reader.

\ansno 3. See W. J. \α{LeVeque,} {\sl Topics in Number Theory \bf 2}
(Reading, Mass.: Addison--Wesley, 1956), Chapter↔3.\xskip [{\sl Note:} One
of the men who read a preliminary draft of the manuscript of
this book reported that he had discovered a truly remarkable
proof, which the margin of his copy was too small to contain.]

\ansbegin{3.1}

\ansno 1. (a)\9This will usually fail, since ``round''
telephone numbers are often selected by the telephone user when
possible. In some communities, telephone numbers are perhaps assigned
randomly. But it would be a mistake in any case to try to get several
successive random numbers from the same page, since the same telephone
number is often listed several times in a row.

(b)\9But do you use the left-hand page or the right-hand
page? Say, use the left-hand page number, divide by 2, and take
the units digit. The total number of
pages should be a multiple of 20; but even so, this method will have some bias.

\eject % This gets part of Section 3.1 on the first page of the answers
(c)\9The markings on the faces will slightly bias
the die, but for practical purposes this method is quite satisfactory
(and it has been used by the author in the preparation of several
examples in this set of books). See {\sl Math.\ Comp.\ \bf 15} (1961),
94--95, for further discussion of these dice.

(d)\9(This is a hard question thrown in purposely
as a surprise.)\xskip The number is not quite uniformly random.
If the average number
of emissions per minute is $m$, the probability that the counter
registers↔$k$ is $e↑{-m}m↑k/k!$ (the \α{Poisson distribution}); so
the digit↔0 is selected with probability $e↑{-m} \sum ↓{k≥0}
m↑{10k}/(10k)!$, etc. The units digit will be even with probability
$e↑{-m}\mathop{\hbox{cosh}}m = {1\over2} + {1\over2}e↑{-2m}$, and
this is never equal to ${1}\over{2}$
(although the error is negligibly small when $m$ is large).

(e)\9Okay, provided that the time since the previous
digit selected in this way is random. However, there is possible
bias in borderline cases.

(f,g)\9No, people usually think of certain digits
(like 7) with higher probability.

(h)\9Okay; your assignment of numbers to the horses
had probability $1\over10$ of assigning a given digit to
the winning horse.

\ansno 2. The number of such sequences is the multinomial
coefficient $1000000!/(100000!)↑{10}$; the probability is this
number divided by $10↑{1000000}$, the total number of sequences of a million
digits. By Stirling's approximation we find that the
probability is close to $1/(16π↑410↑{22}\sqrt{2π}) \approx 2.55
\times 10↑{-26}$, about one chance in $4 \times 10↑{25}$.

\ansno 3. 3040504030.

\ansno 4. Step K11 can be entered only from step K10 or step
K2, and in either case we find it impossible for $X$ to be zero
by a simple argument. If $X$ could be zero at that point, the
algorithm would not terminate.

\ansno 5. Since only $10↑{10}$ ten-digit numbers are possible,
some value of $X$ must be repeated during the first $10↑{10} + 1$
steps; and as soon as a value is repeated, the sequence continues
to repeat its past behavior.

\ansno 6. (a)\9Arguing as in the previous exercise, the sequence
must eventually repeat a value; let this repetition occur for
the first time at step $\mu + λ$, where $X↓{\mu+λ} = X↓\mu$.\xskip
(This condition defines $\mu$ and $λ$.) We have $0 ≤ \mu < m$, $0
< λ ≤ m$, $\mu + λ ≤ m$. The values $\mu = 0$, $λ = m$ are attained
iff $f$ is a cyclic permutation; and $\mu = m - 1$, $λ = 1$ occurs, e.g.,
if $X↓0 = 0$, $f(x) = x + 1$ for $x < m - 1$, and $f(m - 1) = m -
1$.

(b)\9We have, for $r ≥ n$, $X↓r = X↓n$ iff $r - n$ is
a multiple of $λ$ and $n ≥ \mu$. Hence $X↓{2n} = X↓n$ iff $n$ is
a multiple of $λ$ and $n ≥ \mu$. The desired results now follow
immediately.\xskip [{\sl Note:} This is essentially a proof of the familiar
mathematical result that the powers of an element in a finite
\α{semigroup} include a unique \α{idempotent} element: take ${X↓0 = a}$,
$f(x) = ax$.]

(c)\9Once $n$ has been found, generate $X↓i$ and $X↓{n+i}$ for $i≥0$ until
first finding $X↓i=X↓{n+i}$; then ${\mu=i}$. If none of the values of $X↓{n+i}$
for $0≤i≤\mu$ is equal to $X↓n$, it follows that $λ=n$, otherwise $λ$ is
the smallest such $i$.

\ansno 7. (a)\9The least $n>0$ such that $n-(\lscr(n)-1)$ is a multiple of $λ$
and $\lscr(n)-1≥\mu$ is $n=2↑{\lceil \lg \max(\mu+1,λ)\rceil}-1+λ$.\xskip [This
may be compared with the least $n>0$ such that $X↓{2n}=X↓n$, namely
$λ\delta↓{\mu0}+\mu+λ-1-\left((\mu+λ-1)\mod λ\right)$.]

(b)\9Start with $X=Y=X↓0$, $k=m=1$.\xskip
$\biglp$At key places in this algorithm we will have
$X=X↓{2m-k-1}$, $Y=X↓{m-1}$, and $m=\lscr(2m-k)$.$\bigrp$\xskip To generate the
next random number, do the following steps: Set $X←f(X)$ and $k←k-1$. If
$X=Y$, stop (the period length $λ$ is equal to $m-k$). Otherwise if $k=0$, set
$Y←X$, $m←2m$, $k←m$. Output $X$.

{\sl Notes:} Brent has also
considered a more general method in which the successive values
of $Y=X↓{n↓i}$ satisfy $n↓1=0$, $n↓{i+1}=1+\lfloor pn↓i\rfloor$ where $p$ is
any number greater than↔1. He showed that the best choice of $p$, approximately
2.4771, saves about 3 percent of the iterations by comparison with $p=2$.\xskip (See
exercise 4.5.4--4.)

The method in part (b) has a serious deficiency, however, since it might generate a
lot of nonrandom numbers before shutting off. For example, we might have a
particularly bad case such as $λ=1$, $\mu=2↑k$. A method based on Floyd's idea
in exercise↔6(b), namely one that maintains $Y=X↓{2n}$ and $X=X↓n$ for
$n = 0$, 1, 2, $\ldotss$, will
require a few more function evaluations than Brent's method, but it will
stop before any number has been output twice.

On the other hand if
$f$ is unknown (e.g., if we are receiving the
values $X↓0$, $X↓1$, $\ldots$ on-line from an outside source) or
if $f$ is difficult to apply, the following cycle detection algorithm
due to R. W. \α{Gosper} will be preferable: Maintain an auxiliary
table $T↓0$, $T↓1$, $\ldotss$, $T↓m$, where $m = \lfloor \lg n\rfloor$
when receiving $X↓n$. Initially $T↓0 ← X↓0$. For $n = 1$, 2, $\ldotss$,
compare $X↓n$ with each of $T↓0$, $\ldotss$, $T↓{\lfloor\lg n\rfloor}$; if
no match is found, set $T↓{e(n)} ← X↓n$, where $e(n) = \max\leftset e\relv
2↑e \hbox{ divides }n+1\rightset$. But if a match $X↓n =
T↓k$ is found, then $λ = n - \max\leftset m \relv  m < n \hbox{ and } e(m) =
k\rightset$.
This procedure does not stop before generating a number twice, but at most $\lceil
{2\over3}λ\rceil$ of the $X$'s will have occurred more than once.\xskip
[MIT AI Laboratory Memo 239 (Feb.\ 29, 1972), Hack 132.]

See also R. \α{Sedgewick} and T. G. \α{Szymanski}, {\sl Proc.\ ACM Symp.\ Th.\
Comp.\ \bf11} (1979), 74--80.

\ansno 8. (a,b)\9$00, 00,\ldots$ [62 starting values]; $10, 10,\ldots$
[19]; $60, 60,\ldots$ [15]; $50, 50,\ldots$ [1]; $24, 57, 24,
57,\ldots$ [3].\xskip (c) 42 or 69; these both lead to a set of fifteen
distinct values, namely (42 or 69), 76, 77, 92, 46, 11, 12,
14, 19, 36, 29, 84, 05, 02, 00.

\ansno 9. Since $X < b↑n$, we have $X↑2 < b↑{2n}$, and the middle square
is $\lfloor X↑2/b↑n\rfloor ≤ X↑2/b↑n$. If $X > 0$, then $X↑2/b↑n <
Xb↑n/b↑n = X$.

\ansno 10. If $X = ab↑n$, the next number of the sequence has
the same form; it is $(a↑2\mod b↑n)b↑n$. If $a$ is a multiple
of $b$ or of all the prime factors of $b$, the sequence will soon
degenerate to zero; if not, the sequence will degenerate into
a cycle of numbers having the same general form as $X$.

Further facts about the middle-square method have
been found by B. \α{Jansson,} {\sl Random Number Generators} (Stockholm:
Almqvist & Wiksell, 1966), Section 3A. Numerologists will
be interested to learn that the number 3792 is self-reproducing
in the four-digit middle-square method, since $3792↑2 = 14379264$;
furthermore (as Jansson has observed), it is ``self-reproducing''
in another sense, too, since its prime factorization is $3\cdot 79 \cdot
2↑4$!

\ansno 11. The probability that $λ = 1$ and $\mu = 0$ is the probability
that $X↓1 = X↓0$, namely $1/m$. The probability that $λ = 1, \mu
= 1$, or $λ = 2, \mu = 0$, is the probability that $X↓1 ≠ X↓0$
and that $X↓2$ has a certain value, so it is $(1 - 1/m)(1/m)$.
Similarly, the probability that the sequence has any given $\mu$
and $λ$ is a function only of $\mu + λ$, namely
$$P(\mu , λ) = {1\over m}\prod ↓{1≤k<\mu +λ}\left(1-{k\over m}\right).$$

For the probability that $λ = 1$, we have
$$\sum ↓{\mu ≥0}{1\over m}\prod↓{1≤k≤\mu}\left(1-{k\over m}\right)
={1\over m}Q(m),$$
where $Q(m)$ is defined in Section 1.2.11.3, Eq.\
(2). By Eq.\ (25) in that section, the probability is approximately
$6\sqrt{π/2m} \approx 1.25/\sqrt{m}$. The chance of Algorithm↔K converging
as it did is only about one in 80000; the author was decidedly
unlucky. But see exercise↔15 for further comments on the ``colossalness.''

%\ansno 12. This answer begins with an aligned equation.
\penalty-200\vskip 12pt plus 6pt minus 6pt
\halign{\hbox to 19pt{\hfill#}⊗\quad\hfill$\dispstyle#$⊗$\dispstyle\;#$\hfill\cr
{\bf 12.}⊗\sum↓{\scriptstyle 1≤λ≤m \atop \scriptstyle 0≤\mu<m}λP(\mu,λ)⊗
={1\over m}\left(1+3\left(1-{1\over m}\right)+6\left(1-{1\over m}\right)
\left(1-{2\over m}\right)+\cdots\right)\cr
⊗⊗={1+Q(m) \over 2}.\cr}
\vskip 9 pt plus 6pt minus 6pt
\noindent
(See the previous answer. In general if $f(a↓0, a↓1,\ldotss) = \sum↓{n≥0}a↓n
\prod ↓{1≤k≤n}(1 - k/m)$ then $f(a↓0,
a↓1,\ldotss) = a↓0 + f(a↓1, a↓2,\ldotss) - f(a↓1, 2a↓2,\ldotss)/m$;
apply this identity with $a↓n = (n + 1)/2$.) Therefore the average
value of $λ$ (and, by symmetry of $P(\mu , λ)$, also of $\mu + 1$)
is approximately $\sqrt{πm/8}+ {1\over 3}$. The average value
of $\mu + λ$ is exactly $Q(m)$, approximately $\sqrt{πm/2} - {1\over 3}$.\xskip
[For alternative derivations and further results, including asymptotic
values for the moments, see A. \α{Rapoport,} {\sl Bull.\ Math.\ Biophysics
\bf 10} (1948), 145--157, and B. \α{Harris,} {\sl Annals Math.\ Stat.\ 
\bf 31} (1960), 1045--1062; see also I.↔M. \α{Sobol',} {\sl Theory of
Probability and its Applications \bf 9} (1964), 333--338. Sobol'
discusses the asymptotic period length for the more general
sequence $X↓{n+1} = f(X↓n)$ if $n \neqv 0 \modulo{m};\ X↓{n+1}
= g(X↓n)$ if $n ≡ 0 \modulo{m}$; with both $f$ and $g$ random.]

\ansno 13. [Paul \α{Purdom} and John \α{Williams,} {\sl Trans.\ Amer.\ Math.\ 
Soc.\ \bf 133} (1968), 547--551.]\xskip Let $T↓{mn}$ be the number
of functions that have $n$ one-cycles and no cycles of length
greater than one. Then$$
T↓{mn}={m-1\choose n-1}\,m↑{m-n}.$$
(See Section 2.3.4.4.) {\sl Any} function is such a function followed by a
permutation of the $n$ elements that were the one-cycles. Hence $\sum↓{n≥1}
T↓{mn}\,n! = m↑m$.

Let $P↓{nk}$ be the number of permutations of $n$ elements in which the
longest cycle is of length $k$. Then the number of functions with a maximum
cycle of length $k$ is $\sum↓{n≥1}T↓{mn}P↓{nk}$. To get the average value of
$k$, we compute $\sum↓{k≥1}\sum↓{n≥1}kT↓{mn}P↓{nk}$, which by the result of
exercise 1.3.3--23 is $\sum↓{n≥1}T↓{mn}\,n!(n+{1\over 2}+ε↓n)c$
where $c \approx .62433$ and
$ε↓n→0$ as $n→∞$. Summing, we get the average value $cQ(m)+{1\over 2}c+\delta↓m$,
where
$\delta↓m→0$ as $m→∞$.\xskip (This is not substantially larger than the average
value when $X↓0$ is selected at random. The average value of $\max(\mu+λ)$ is
still unknown.)
% Vicinity of page 519
% folio 654 galley 2 	*
\ansno 14.  Let $c↓r(m)$ be the number of
functions with exactly $r$ different final cycles. From the
recurrence $c↓1(m) = (m - 1)! - \sum ↓{k>0}{m\choose k}(-1)↑k(m
- k)↑kc↓1(m - k)$, which comes by counting the number of functions
whose image contains at most $m - k$ elements, we find the solution
$c↓1(m) = m↑{m-1}Q(m)$.\xskip (Cf.\ exercise 1.2.11.3--16.)\xskip Another
way to obtain the value of $c↓1(m)$, which is perhaps more elegant
and revealing, is given in exercise \hbox{2.3.4.4--17}. The value of
$c↓r(m)$ may be determined by solving the recurrence
$$c↓r(m) = \sum ↓{0<k<m}{m-1\choose k-1}c↓1(k)c↓{r-1}(m-k),$$
which has the solution
$$c↓r(m) = m↑{m-1}\left({1\over 0!}{1\comb[]r}
+ {1\over 1!}{2\comb[]r}{m - 1\over m} + {1\over
2!}{3\comb[]r} {m - 1\over m} {m - 2\over m} + \cdots\right).$$
The desired average value can now be computed;
it is (cf.\ exercise↔12)
$$\eqalign{E↓m⊗= {1\over m} \left(H↓1 + 2H↓2 {m
- 1\over m} + 3H↓3 {m - 1\over m} {m - 2\over m} + \cdots\right)\cr
⊗= 1 + {1\over 2} {m - 1\over m} + {1\over 3} {m - 1\over m}
{m - 2\over m} + \cdotss.\cr}$$
This latter formula was obtained by quite different
means by Martin D. \α{Kruskal,} {\sl AMM \bf 61} (1954), 392--397.
Using the integral representation
$$E↓m = \int ↑{∞}↓{0}\left(\left(
1 + {x\over m}\right)↑m - 1\right)\, e↑{-x}\, {dx\over x},$$
he proved the asymptotic relation
$\lim↓{m→∞} (E↓m - {1\over 2}\ln m) = {1\over 2}(\gamma
+\ln 2)$.
For further results and references, see John \α{Riordan,}
{\sl Annals Math.\ Stat.\ \bf 33} (1962), 178--185.

\ansno 15.  The probability that $f(x) ≠ x$ for all $x$
is ($m - 1)↑m/m$, which is approximately $1/e$. The existence
of a self-repeating value in an algorithm like Algorithm↔K is
therefore not ``colossal'' at all---it occurs with probability
$1 - 1/e \approx .63212$. The only ``colossal'' thing was that
the author happened to hit such a value when $X↓0$ was chosen
at random (see exercise↔11).

\ansno 16.  The sequence will repeat when a pair of successive
elements occurs for the second time. The maximum period is $m↑2$.\xskip
(Cf.\ next exercise.)

\ansno 17.  After selecting $X↓0, \ldotss , X↓{k-1}$ arbitrarily,
let $X↓{n+1} = f(X↓n, \ldotss , X↓{n-k+1})$, where $0 ≤ x↓1,
\ldotss , x↓k < m$ implies that $0 ≤f(x↓1, \ldotss , x↓k) < m$.
The maximum period is $m↑k$. This is an obvious upper bound,
but it is not obvious that it can be attained; for a proof that
it can always be attained for suitable↔$f$, see exercises 3.2.2--17
and 3.2.2--21, and for the number of ways to attain it see exercise
2.3.4.2--23.

\ansno 18. Same as exercise↔7, but use the $k$-tuple of elements
$(X↓n,\ldotss,X↓{n-k+1})$
in place of the single element $X↓n$.

\ansbegin{3.2.1}

\ansno 1. Take $X↓0$ even, $a$
even, $c$ odd. Then $X↓n$ is odd for $n > 0$.

\ansno 2.  Let $X↓r$ be the first repeated value in the
sequence. If $X↓r$ were equal to $X↓k$ for some $k$ where
$0 < k < r$, we could prove that
$X↓{r-1} = X↓{k-1}$, since $X↓n$ uniquely determines $X↓{n-1}$
when $a$ is prime to $m$. Hence $k = 0$.

\ansno 3. If $d$ is the greatest common
divisor of $a$ and $m$, the quantity $aX↓n$ can take on at most
$m/d$ values. The situation can be even worse; e.g., if $m =
2↑e$ and if $a$ is even, Eq.↔(6) shows that the sequence is
eventually constant.

\ansno 4.  Induction on $k$.

\ansno 5.  If $a$ is relatively prime to $m$, there is
a number $a↑\prime$ for which $aa↑\prime ≡ 1 \modulo{m}$. Then
$X↓{n-1} = (a↑\prime X↓n - a↑\prime c)\mod m$, and in general,
$$\eqalign{X↓{n-k}⊗=\left( (a↑\prime )↑kX↓n - c(a↑\prime + \cdots
+ (a↑\prime )↑k)\right)\mod m\cr ⊗= \left((a↑\prime
)↑kX↓n - c {(a↑\prime )↑{k+1} - a↑\prime \over a↑\prime - 1}\right)\mod
m\cr}$$
when $k > 0$, $n - k ≥ 0$. If $a$ is not relatively prime
to $m$, it is not possible to determine $X↓{n-1}$ when $X↓n$
is given; multiples of $m/\gcd(a, m)$ may be added to
$X↓{n-1}$ without changing the value of $X↓n$.\xskip (See also exercise
3.2.1.3--7.)

\ansbegin{3.2.1.1}

\ansno 1. Let $c↑\prime$ be a
solution to the congruence $ac↑\prime ≡ c \modulo{m}$.\xskip (Thus,
$c↑\prime = a↑\prime c\mod m$, if $a↑\prime$ is the number in
the answer to exercise 3.2.1--5.)\xskip Then we have
$$\vcenter{\mixtwo{LDA⊗X\cr
ADD\ ⊗CPRIME\cr
MUL⊗A⊗\blackslug\cr}}$$
Overflow is possible on this addition operation.\xskip (From results derived later
in the chapter, it is probably best to save a unit of time, taking $c=a$ and
replacing the {\tt ADD}
instruction by ``{\tt INCA 1}''.  Then if $X↓0=0$, overflow will not occur
until the end of the period, so it won't occur in practice.)

\mixans 2. {⊗RANDM⊗STJ⊗1F\cr
⊗⊗LDA⊗XRAND\cr
⊗⊗MUL⊗A\cr
⊗⊗SLAX⊗5\cr
⊗⊗ADD⊗C⊗(or, \.{INCA} $c$, if $c$ is small)\cr
⊗⊗STA⊗XRAND\cr
⊗1H⊗JNOV⊗*\cr
⊗⊗JMP⊗*-1\cr
⊗XRAND⊗CON⊗$X↓0$\cr
⊗A⊗CON⊗$a$\cr
⊗C⊗CON⊗$c$⊗\blackslug\cr}
\yyskip
\noindent{\sl Note:} Locations \.A and \.C should probably be named
\.{2H} and \.{3H} to avoid conflict with other symbols, if this subroutine
is to be used by other programmers.

\ansno 3.  See \.{WM1} at the end of Program 4.2.3D.

\ansno 4.  \def\\{\<\,\mathbin{\underline{\char'155\char'157\char'144}}\<\,}
Define the operation $x\\2↑e = y$ iff
$x ≡ y\modulo{2↑e}$ and $-2↑{e-1} ≤ y < 2↑{e-1}$. The congruential
sequence $\langle Y↓n\rangle$ defined by
$$Y↓0 = X↓0\\2↑{32},\qquad Y↓{n+1} = (aY↓n + c)\\2↑{32}$$
is easy to compute on 370-style machines, since
the lower half of the product of $y$ and $z$ is $(yz)\\2↑{32}$
for all two's complement numbers $y$ and $z$, and since addition
ignoring overflow also delivers its result $\!\null\\ 2↑{32}$. This
sequence has all the randomness properties of the standard linear
congruential sequence $\langle X↓n\rangle $, since $Y↓n ≡ X↓n\modulo
{2↑{32}}$. Indeed, the two's complement representation of $Y↓n$
is {\sl identical} to the binary representation of $X↓n$, for
all $n$.\xskip [G. \α{Marsaglia} and T. A. \α{Bray} first pointed this
out in {\sl CACM \bf 11} (1968), 757--759.]

\ansno 5.  (a)\9 Subtraction: \.{LDA X;} \.{SUB Y;} \.{JANN *+2;}
\.{ADD M}.\xskip (b) Addition: \.{LDA X;} \.{SUB M;} \.{ADD Y;} \.{JANN
*+2;} \.{ADD M}.\xskip (Note that if $m$ is more than half the word size,
the instruction
``\.{SUB M}'' must precede the instruction ``\.{ADD Y}''.)

\ansno 6.  The sequences are not essentially different,
since adding the constant $(m - c)$ has the same effect as subtracting
the constant $c$. The operation must be combined with
multiplication, so a subtractive process has little merit over
the additive one (at least in \MIX's case), except when it is
necessary to avoid affecting the overflow toggle.

\ansno 7.  The prime factors of $z↑k - 1$ appear in the
factorization of $z↑{kr} - 1$. If $r$ is odd, the prime factors
of $z↑k + 1$ appear in the factorization of $z↑{kr} + 1$. And
$z↑{2k} - 1$ equals
$(z↑k - 1)(z↑k + 1)$.

%\ansno 8. appears within the following alignment.
\anskip
\halign{\hbox to 19pt{#}⊗\lft{\tt#}\quad⊗\lft{\tt#}\quad⊗
\lft{\rm#}\cr
{\hfill\bf 8. }⊗JOV⊗*+1
⊗(Ensure that overflow is off.)\cr
⊗LDA⊗X\cr
⊗MUL⊗A\cr
⊗STX⊗TEMP\cr
⊗ADD⊗TEMP⊗Add lower half to upper half.\cr
⊗JNOV⊗*+2⊗If $≥w$, subtract $w - 1$.\cr
⊗INCA⊗1⊗(Overflow is impossible in this step.)\quad\blackslug\cr}
\yyskip
\noindent{\sl Note:} Since addition on an $e$-bit
ones'-complement computer is $\mod\;(2↑e - 1)$, it is possible
to combine the techniques of exercises 4 and↔8, producing $(yz)\mod(2↑e
- 1)$ by adding together the two $e$-bit halves of the product
$yz$, for all ones' complement numbers $y$ and $z$ regardless
of sign.

\ansno 9.  The pairs $(0, w - 2)$, $(1, w - 1)$ are treated
as equivalent in input and output:

\yyskip
\halign{\hbox to 19pt{#}⊗\lft{\tt#}\quad⊗\lft{\tt#}\quad⊗
\lft{\rm#}\cr
⊗JOV⊗*+1\cr
⊗LDA⊗X\cr
⊗MUL⊗A⊗$aX = qw + r.$\cr
⊗SLC⊗5⊗$\rA ← r$, $\rX ← q$.\cr
⊗STX⊗TEMP\cr
⊗ADD⊗TEMP\cr
⊗JNOV⊗*+2⊗Get $(r + q)\mod(w - 2)$.\cr
⊗INCA⊗2⊗Overflow is impossible.\cr
⊗ADD⊗TEMP\cr
⊗JNOV⊗*+3⊗Get $(r + 2q)\mod(w - 2)$.\cr
⊗INCA⊗2⊗Overflow is possible.\cr
⊗JOV⊗*-1⊗\hskip4.5cm\blackslug\cr}
% Vicinity of page 522
% folio 659 galley 3 	*
\ansbegin{3.2.1.2}

\ansno 1. Period length $m$,
by Theorem↔A\null.\xskip (Cf.\ exercise↔3.)

\ansno 2.  Yes, these conditions imply the conditions
in Theorem↔A\null, since the only prime divisor of $2↑e$ is 2, and
any odd number is relatively prime to $2↑e$.\xskip (In fact, the conditions
of the exercise are {\sl necessary} and sufficient.)

\ansno 3.  By Theorem↔A\null, we need $a ≡ 1 \modulo{4}$ and
$a ≡ 1\modulo{5}$. By Law↔D of Section 1.2.4, this is equivalent
to $a ≡ 1\modulo{20}$.

\ansno 4.  We know $X↓{2↑{e-1}} ≡ 0
\modulo{2↑{e-1}}$ by using Theorem↔A in the case $m = 2↑{e-1}$.
Also using Theorem↔A for $m = 2↑e$, we know that $X↓{2↑{e-1}}
\neqv 0\modulo{2↑e}$. It follows
that $X↓{2↑{e-1}} = 2↑{e-1}$. More generally,
we can use Eq. 3.2.1--6 to prove that the second half of the
period is essentially like the first half, since $X↓{n+2↑{e-1}}
= (X↓n + 2↑{e-1})\mod 2↑e$.\xskip (The quarters
are similar too, see exercise↔21.)

\ansno 5.  We need $a ≡ 1 \modulo{p}$ for $p = 3, 11,
43, 281, 86171$. By Law D of Section 1.2.4, this is equivalent
to $a ≡ 1 \modulo{3 \cdot 11 \cdot 43 \cdot 281 \cdot 86171}$, so the {\sl
only} solution is the terrible multiplier $a = 1$.

\ansno 6.  (Cf.\ previous exercise.) $a ≡ 1 \modulo {3\cdot
7 \cdot 11 \cdot 13 \cdot 37}$ implies that the solutions are $a =
1 + 111111k$, for $0 ≤ k ≤ 8$.

\ansno 7.  Using the notation of the proof of Lemma↔Q\null,
$\mu$ is the smallest value such that $X↓{\mu+λ} = X↓\mu$;
so it is the smallest value such that $Y↓{\mu+λ} = Y↓\mu$
and $Z↓{\mu+λ} = Z↓\mu$. This shows that $\mu = \max(\mu
↓1, \ldotss , \mu ↓t)$. The highest achievable $\mu$ is $\max(e↓1,
\ldotss , e↓t)$, but nobody really wants to achieve it.

\ansno 8. We have $a↑2 ≡ 1 \modulo{8}$; so $a↑4 ≡ 1 \modulo
{16}$, $a↑8 ≡ 1 \modulo{32}$, etc. If ${a \mod 4 = 3}$, then $a - 1$ is
twice an odd number; so $(a↑{2↑{e-1}} - 1)/2 ≡ 0 \modulo
{2↑{e+1}/2}$, and this yields the desired result.

\ansno 9.  Substitute for $X↓n$ in terms of $Y↓n$ and
simplify. If $X↓0$ mod 4 = 3, the formulas of the exercise do
not apply; but they do apply to the sequence $Z↓n = (-X↓n)\mod
2↑e$, which has essentially the same behavior.

\ansno 10.  Only $m = 1$, 2, 4, $p↑e$, and $2p↑e$, for odd
primes $p$. In all other cases, the result of Theorem↔B is an
improvement over \α{Euler's theorem} (exercise 1.2.4--28).

\ansno 11.  (a)\9 Either $x + 1$ or $x - 1$ (not both) will
be a multiple of 4, so $x \mp 1 = q2↑f$, where $q$ is odd and
$f$ is greater than 1.\xskip (b) In the given circumstances, $f <
e$ and so $e ≥ 3$. We have $\pm x ≡ 1 \modulo{2↑f}$ and $\pm
x \neqv 1 \modulo{2↑{f+1}}$ and $f > 1$. Hence by applying
Lemma↔P\null, we find that $(\pm x)↑{2e-f-1} \neqv 1 \modulo
{2↑e}$, while $x↑{2e-f} = (\pm x)↑{2e-f} ≡ 1 \modulo {2↑e}$.
So the order is a divisor of $2↑{e-f}$, but not a divisor of
$2↑{e-f-1}$.\xskip (c) 1 has order 1; $2↑e - 1$ has order 2; the maximum
period when $e ≥ 3$ is therefore $2↑{e-2}$, and for $e≥4$ it is necessary to
have $f = 2$, that is, $x ≡ 4 \pm 1 \modulo {8}$.

\ansno 12.  If $k$ is a proper divisor of $p - 1$ and
if $a↑k ≡ 1 \modulo{p}$, then by Lemma↔P we have $a↑{kp↑{e-1}}
≡ 1 \modulo {p↑e}$. Similarly, if $a↑{p-1}
≡ 1 \modulo {p↑2}$, we find that $a↑{(p-1)p↑{e-2}}
≡ 1 \modulo {p↑e}$. So in these cases $a$ is {\sl
not} primitive. Conversely, if $a↑{p-1} \neqv 1 \modulo
{p↑2}$, Theorem 1.2.4F and Lemma↔P tell us that $a↑{(p-1)p↑{e-2}}
\neqv 1 \modulo {p↑e}$, but $a↑{(p-1)p↑{e-1}}
≡ 1 \modulo {p↑e}$. So the order is a divisor
of $(p - 1)p↑{e-1}$ but not of $(p - 1)p↑{e-2}$; it therefore
has the form $kp↑{e-1}$, where $k$ divides $p - 1$. But if $a$
is primitive modulo $p$, the congruence $a↑{kp↑{e-1}}
≡ a↑k ≡ 1 \modulo {p}$ implies that $k = p - 1$.

\ansno 13.  Let $λ$ be the order of $a$ modulo $p$. By
Theorem 1.2.4F\null, $λ$ is a divisor of $p - 1$. If $λ < p - 1$, then
$(p - 1)/λ$ has a prime factor, $q$.

\ansno 14.  Let $0 < k < p$. If $a↑{p-1} ≡ 1 \modulo
{p↑2}$, then $(a + kp)↑{p-1} ≡ a↑{p-1} + {(p - 1)}\*a↑{p-2}kp \modulo
{p↑2}$; and this is $\neqv 1$, since $(p - 1)a↑{p-2}k$ is
not a multiple of $p$. By exercise↔12, $a + kp$ is primitive
modulo $p↑e$.

\ansno 15. (a)\9 If $λ↓1 = p↑{e↓1}↓{1} \ldotss p↑{e↓t}↓{t},
λ↓2 = p↑{f↓1}↓{1} \ldotss p↑{f↓t}↓{t}$, let $\kappa ↓1 = p↑{g↓1}↓{1}
\ldotss p↑{g↓t}↓{t}, \kappa ↓2 = p↑{h↓1}↓{1} \ldotss p↑{h↓t}↓{t}$,
where$$\vbox{
\halign{$#$⊗\lft{$\;#$}⊗\quad#\quad⊗$#$⊗\lft{$\;#$}⊗\qquad if\quad$#$\cr
g↓j⊗=e↓j⊗and⊗h↓j⊗=0,⊗e↓j<f↓j,\cr
g↓j⊗=0⊗and⊗h↓j⊗=f↓j,⊗e↓j≥f↓j.\cr}}$$
Now $a↑{\kappa ↓1}↓{1}, a↑{\kappa ↓2}↓{2}$ have periods
$λ↓1/\kappa ↓1, λ↓2/\kappa ↓2$, and the latter are relatively
prime. Fur\-ther\-more $(λ↓1/\kappa ↓1)(λ↓2/\kappa ↓2) = λ$, so it suffices
to consider the case when $λ↓1$ is relatively prime to $λ↓2$,
that is, when $λ = λ↓1λ↓2$. Now since $(a↓1a↓2)↑λ≡1$, we
have $1 ≡ (a↓1a↓2)↑{λλ↓1} ≡ a↑{λλ↓1}↓{2}$; hence $λλ↓1$
is a multiple of $λ↓2$. This implies that $λ$ is a multiple
of $λ↓2$, since $λ↓1$ is relatively prime to $λ↓2$. Similarly,
$λ$ is a multiple of $λ↓1$; hence $λ$ is a multiple of $λ↓1λ↓2$.
But obviously $(a↓1a↓2)↑{λ↓1λ↓2} ≡ 1$, so $λ
= λ↓1λ↓2$.

(b)\9 If $a↓1$ has order $λ(m)$ and if $a↓2$
has order $λ$, by part (a) $λ(m)$ must be a multiple of $λ$,
otherwise we could find an element of higher order, namely
of order lcm$\left(λ, λ(m)\right)$.

\ansno 16. (a)\9 $f(x) = (x
- a)\biglp x↑{n-1} + (a + c↓1)x↑{n-2} + \cdots + (a↑{n-1}
+ \cdots + c↓{n-1})\bigrp + f(a)$.\xskip (b) The statement is clear
when $n = 0$. If $a$ is one root,
$f(x) ≡ (x - a)q(x)$;
therefore if $a↑\prime$ is any other root,
$$0 ≡ f(a↑\prime ) ≡ (a↑\prime - a)q(a↑\prime ),$$
and since $a↑\prime - a$ is not a multiple of $p$,
$a↑\prime$ must be a root of $q(x)$. So if $f(x)$ has more than
$n$ distinct roots, $q(x)$ has more than $n - 1$ distinct roots.\xskip
(c) $λ(p) ≥ p - 1$, since $f(x)$ must have degree $≥p - 1$ in
order to possess so many roots. But by Theorem 1.2.4F\null, $λ(p)
≤ p - 1$.

\ansno 17.  By Lemma↔P\null, $11↑5 ≡ 1 \modulo{25}$, $11↑5 \neqv
1 \modulo{125}$, etc.; so the order of 11 is $5↑{e-1} \modulo
{5↑e}$, not the maximum value $λ(5↑e) = 4 \cdot 5↑{e-1}$. But by
Lemma↔Q the total period length is the least common multiple
of the period modulo $2↑e$ (namely $2↑{e-2}$) and the period
modulo $5↑e$ (namely $5↑{e-1}$), and this is $2↑{e-2}5↑{e-1}
= λ(10↑e)$. The period modulo $5↑e$ may be $5↑{e-1}$ or $2\cdot 5↑{e-1}$
or $4\cdot 5↑{e-1}$, without affecting the length of period modulo
$10↑e$, since the least common multiple is taken. The values
that are primitive modulo $5↑e$ are those congruent to 2, 3,
8, 12, 13, 17, 22, 23 modulo 25 (cf.\ exercise↔12), namely 3,
13, 27, 37, 53, 67, 77, 83, 117, 123, 133, 147, 163, 173, 187,
197.

\ansno 18.  According to Theorem↔C\null, $a \mod 8$ must
be 3 or 5. Knowing the period of $a$ modulo↔5 and modulo 25
allows us to apply Lemma↔P to determine admissible values of
$a$ mod↔25. Period $= 4 \cdot 5↑{e-1}$: 2, 3, 8, 12, 13, 17, 22,
23; period $= 2 \cdot 5↑{e-1}$: 4, 9, 14, 19; period $= 5↑{e-1}$:
6, 11, 16, 21. Each of these 16 values yields one value of
$a$, $0 ≤ a < 200$, with $a \mod 8 = 3$, and another value of $a$
with $a \mod 8 = 5$.

\ansno 19. One example appears in Table 3.3.4--1, line 26.

\ansno 20.  (a)\9 We have $AY↓n + X↓0 ≡ AY↓{n+k} + X↓0 \modulo
{m}$ iff $Y↓n ≡ Y↓{n+k} \modulo {m↑\prime}$.\xskip (b)(i) Obvious.\xskip
(ii) Theorem↔A.\xskip (iii) $(a↑n - 1)/(a - 1) ≡ 0 \modulo {2↑e}$
iff $a↑n ≡ 1 \modulo {2↑{e+1}}$; if $a \neqv -1$,
the order of $a$ modulo $2↑{e+1}$ is twice its order modulo↔$2↑e$.\xskip
(iv) $(a↑n - 1)/(a - 1) ≡ 0 \modulo {p↑e}$ iff $a↑n
≡ 1$.

\ansno 21. $X↓{n+s} ≡ X↓n+X↓s$ by Eq.\ 3.2.1--6; and $s$ is a divisor of
$m$, since $s$ is a power of $p$ when $m$ is a power of $p$. Hence
a given integer $q$ is a multiple of $m/s$ iff $X↓{qs} ≡ 0$ iff $q$ is
a multiple of $m/\gcd(X↓s,m)$.

\ansbegin{3.2.1.3}

\ansno 1. $c = 1$ is always relatively
prime to $B↑5$; and every prime dividing $m = B↑5$ is a divisor
of $B$, so it divides $b = B↑2$ to at least the second power.

\ansno 2.  Only 3, so the generator is not recommended in spite
of its long period.

\ansno 3.  The potency is 18 in both cases (see next exercise).

\ansno 4.  Since $a \mod 4 = 1$, we must have $a \mod 8
= 1$ or 5, so $b \mod 8 = 0$ or 4. If $b$ is an odd multiple of
4, and if $b↓1$ is a multiple of 8, clearly $b↑s ≡ 0 \modulo
{2↑e}$ implies that $b↑{s}↓{1} ≡ 0 \modulo {2↑e}$, so $b↓1$
cannot have higher potency.

\ansno 5.  The potency is the smallest value of $s$ such
that $f↓js ≥ e↓j$ for all $j$.

\ansno 6.  The modulus must be divisible by $2↑7$ or by $p↑4$ (for
odd prime $p$) in order to have a potency as high as 4. The
only values are $m = 2↑{27} + 1$ and $10↑9 - 1$.

\ansno 7.  $a↑\prime = (1 - b + b↑2 - \cdots)\mod m$,
where the terms in $b↑s, b↑{s+1}$, etc., are dropped (if $s$
is the potency).

\ansno 8.  Since $X↓n$ is always odd,
$$X↓{n+2} = (2↑{34} + 3 \cdot 2↑{18} + 9)X↓n \mod 2↑{35} = (2↑{34}
+ 6X↓{n+1} - 9X↓n)\mod 2↑{35}.$$
Given $Y↓n$ and $Y↓{n+1}$, the possibilities for
$$Y↓{n+2} \approx \left( 5 + 6(Y↓{n+1} + \epsilon ↓1) - 9(Y↓n
+ \epsilon ↓2)\right)\mod 10,$$
with $0 ≤ \epsilon ↓1 < 1$, $0 ≤ \epsilon ↓2 < 1$,
are limited and nonrandom.

{\sl Note:} If the multiplier suggested in exercise↔3
were, say, $2↑{33} + 2↑{18} + 2↑2 + 1$, instead of $2↑{23} +
2↑{14} + 2↑2 + 1$, we would similarly find $X↓{n+2} - 10X↓{n+1}
+ 25X↓n ≡\hbox{constant}\modulo{2↑{35}}$. In general, we do not
want $a \pm \delta$ to be divisible by high powers of 2 when
$\delta$ is small, else we get ``second order impotency.'' See
Section 3.3.4 for a more detailed discussion.

The generator that appears in this exercise is
discussed in an article by \α{MacLaren} and \α{Marsaglia,} {\sl JACM \bf 12}
(1965), 83--89. The deficiencies of such generators were first
demonstrated by M. \α{Greenberger,} {\sl CACM \bf 8} (1965), 177--179.
Yet generators like this were still in widespread use
more than ten years later (cf.\ the discussion of \.{\α{RANDU}} in
Section 3.3.4).
% Vicinity of page 525
% folio 662 galley 4  	*
\ansbegin{3.2.2}

\ansno 1. The method is useful
only with great caution. In the first place, $aU↓n$ is likely
to be so large that the addition of $c/m$ that follows will
lose almost all significance, and the ``mod 1'' operation will
nearly destroy any vestiges of significance that might remain.
We conclude that double-precision floating point arithmetic is necessary.
Even with double precision, one must be sure that no rounding, etc.,
occurs to affect the numbers of the sequence in any way, since
that would destroy the theoretical grounds for the good behavior
of the sequence.\xskip (But see exercise↔23.)

\ansno 2.  $X↓{n+1}$ equals either $X↓{n-1} + X↓n$ or
$X↓{n-1} + X↓n - m$. If $X↓{n+1} < X↓n$ we must have $X↓{n+1}
= X↓{n-1} + X↓n - m;$ hence $X↓{n+1} < X↓{n-1}$.

\ansno 3. (a)\9 The underlined numbers are $V[j]$ after step M3.
\def\\#1{$\underline{#1}$}
\def\0{\hskip 4.5pt} 
\def\3{$\ldots$}
$$\vbox{\baselineskip0pt\lineskip0pt\halign{\tabskip 4.5pt
\rt{#}⊗\rt{#}⊗#⊗\lft{#}\tabskip0pt\cr
\noalign{\hrule}
Output:⊗initial⊗\vrule height 10.25pt depth 4pt⊗
0\04\05\06\02\00\03\hbox to 4.5pt{\hfill(}2\07\04\0
1\06\03\00\05)\qquad and repeats.\cr
\noalign{\hrule}
$V[0]$:⊗0⊗\vrule height 10.25pt depth 3pt⊗
\\4\0\\7\07\07\07\07\07\07\0\\4\0\\7\07\07\07\07\07\07\0\\4\0\\7\0\3\cr
$V[1]$:⊗3⊗\vrule height 9.25pt depth 3pt⊗
3\03\03\03\03\03\0\\2\0\\5\05\05\05\05\05\05\0\\2\0\\5\05\05\0\3\cr
$V[2]$:⊗2⊗\vrule height 9.25pt depth 3pt⊗
2\02\02\02\0\\0\0\\3\03\03\03\03\03\03\0\\0\0\\3\03\03\03\03\0\3\cr
$V[3]$:⊗5⊗\vrule height 9.25pt depth 4pt⊗
5\05\0\\6\0\\1\01\01\01\01\01\01\0\\6\0\\1\01\01\01\01\01\01\0\3\cr
\noalign{\hrule}
$X$:⊗⊗\vrule height 10.25pt depth 3pt⊗
4\07\06\01\00\03\02\05\04\07\06\01\00\03\02\05\04\07\0\3\cr
$Y$:⊗⊗\vrule height 9.25pt depth 4pt⊗
0\01\06\07\04\05\02\03\00\01\06\07\04\05\02\03\00\01\0\3\cr
\noalign{\hrule}}}$$
So the potency has been reduced to 1! (See further comments in the
answer to exercise↔15.)

(b)\9 The underlined numbers are $V[j]$ after step B2.
$$\vbox{\baselineskip0pt\lineskip0pt\halign{
\tabskip 4.5pt\rt{#}⊗\rt{#}⊗#⊗\lft{#}\cr
\noalign{\hrule}
Output:⊗initial⊗\vrule height 10.25pt depth 4pt⊗
2\03\06\05\07\00\00\05\03\0\3\04\06\hbox to 4.5pt{\hfill(}3\0
0\0\3\04\07\hbox to 4.5pt{)\hfill}\3\cr
\noalign{\hrule}
$V[0]$:⊗0⊗\vrule height 10.25pt depth 3pt⊗
0\00\00\00\00\00\0\\5\0\\4\04\0\3\01\01\01\01\0\3\01\01\0\3\cr
$V[1]$:⊗3⊗\vrule height 9.25pt depth 3pt⊗
3\0\\6\0\\1\01\01\01\01\01\01\0\3\00\00\00\0\\4\0\3\00\00\0\3\cr
$V[2]$:⊗2⊗\vrule height 9.25pt depth 3pt⊗
\\7\07\07\07\0\\3\03\03\03\0\\7\0\3\06\0\\2\02\02\0\3\07\0\\2\0\3\cr
$V[3]$:⊗5⊗\vrule height 9.25pt depth 4pt⊗
5\05\05\0\\0\00\0\\2\02\02\02\0\3\0\\3\03\0\\5\05\0\3\0\\3\03\0\3\cr
\noalign{\hrule}
$X$:⊗4⊗\vrule height 10.25pt depth 4pt⊗
7\06\01\00\03\02\05\04\07\0\3\03\02\05\04\0\3\03\02\0\3\cr
\noalign{\hrule}}}$$
In this case the output is considerably better than the input; it enters a
repeating cycle of length 40 after 46 steps: 236570 05314 72632 40110 37564
76025 12541 73625 03746 (30175 24061 52317 46203 74531 60425 16753 02647).
The cycle can be found easily by applying the method of exercise 3.1--7 to the
above array until a column is repeated.

\ansno 4.  The low-order byte of many random sequences
(e.g., linear congruential sequences with $m = \hbox{word size}$) is
much less random than the high-order byte. See Section 3.2.1.1.

\ansno 5.  The randomizing effect would be quite minimized,
because $V[j]$ would always contain a number in a certain
range, essentially $j/k ≤ V[j]/m < (j + 1)/k$. However, some
similar approaches could be used: we could take $Y↓n = X↓{n-1}$,
or we could choose↔$j$ from $X↓n$ by extracting some digits
from about the middle instead of at the extreme left. None of
these suggestions would produce a lengthening of the period analogous
to the behavior of Algorithm↔B.

\ansno 6.  For example, if $\.X↓n/m < {1\over 2}$, then
$\.X↓{n+1} = 2\.X↓n$.

\ansno 7.  [W. \α{Mantel,} {\sl Nieuw Archief voor Wiskunde}
(2) {\bf 1} (1897), 172--184.]$$
\def\\{\hskip 4.5pt}
\hbox{
\vbox{\halign{\rt{#}\cr
The subsequence of\cr
\.X values:\cr}}
\quad
$\vcenter{\halign{\ctr{#}\cr
00\301\cr 00\310\cr .\\.\\.\cr 10\300\cr \.{CONTENTS(A)}\cr}}$
\quad becomes:\quad
$\vcenter{\halign{\ctr{#}\cr
00\301\cr 00\310\cr .\\.\\.\cr 10\300\cr 00\300\cr \.{CONTENTS(A)}\cr}}$
}$$

\ansno 8. We may assume that $X↓0 = 0$ and $m = p↑e$,
as in the proof of Theorem 3.2.1.2A\null. First suppose that the
sequence has period length $p↑e$; it follows that the period
of the sequence mod $p↑f$ has length $p↑f$, for $1 ≤ f ≤ e$, otherwise some residues
mod $p↑f$ would never occur. Clearly, $c$ is not a multiple
of $p$, for otherwise each $X↓n$ would be a multiple of $p$.
If $p ≤ 3$, it is easy to establish the necessity of conditions
(iii) and (iv) by trial and error, so we may assume that $p
≥ 5$. If $d \neqv 0 \modulo{p}$ then $dx↑2 + ax + c ≡ d(x
+ a↓1)↑2 + c↓1 \modulo {p↑e}$ for some integers $a↓1$ and $c↓1$
and for all integers $x$; this quadratic takes the same value at the
points $x$ and $-x - 2a↓1$, so it cannot assume all values modulo
$p↑e$. Hence $d ≡ 0 \modulo{p}$; and if $a \neqv 1$,
we would have $dx↑2 + ax + c ≡ x \modulo {p}$ for some $x$,
contradicting the fact that the sequence mod↔$p$ has period
length↔$p$.

To show the sufficiency of the conditions, we
may assume by Theorem 3.2.1.2A and consideration of some trivial
cases that $m = p↑e$ where $e ≥ 2$. If $p = 2$, we have $X↓{n+p}
≡ X↓n + pc \modulo {p↑2}$, by trial; and if $p = 3$, we have
either $X↓{n+p} ≡ X↓n + pc \modulo {p↑2}$, for all $n$, or
$X↓{n+p} ≡ X↓n - pc \modulo {p↑2}$, for all $n$. For $p ≥ 5$,
we can prove that $X↓{n+p} ≡ X↓n + pc \modulo {p↑2}$: Let $d
= pr$, $a = 1 + ps$. Then if $X↓n ≡ cn + pY↓n \modulo {p↑2}$,
we must have $Y↓{n+1} ≡ n↑2c↑2r + ncs + Y↓n \modulo {p}$; hence
$Y↓n ≡ {n\choose 3}2c↑2r + {n\choose 2}(c↑{2}r + cs) \modulo
{p}$. Thus $Y↓p \mod p = 0$, and the desired relation has been
proved.

Now we can prove that the sequence $\langle X↓n\rangle$
of integers defined in the ``hint'' satisfies the relation
$$X↓{n+p↑f} ≡ X↓n + tp↑f\quad \modulo {p↑{f+1}},\qquad
n ≥ 0,$$
for some $t$ with $t \mod p ≠ 0$, and for all
$f ≥ 1$. This suffices to prove that the sequence $\langle X↓n
\mod p↑e\rangle$ has period length $p↑e$, for the length of
the period is a divisor of $p↑e$ but not a divisor of $p↑{e-1}$.
The above relation has already been established for $f = 1$,
and for $f > 1$ it can be proved by induction in the following
manner: Let
$$X↓{n+p↑f} ≡ X↓n + tp↑f + Z↓np↑{f+1}\quad \modulo
{p↑{f+2}};$$
then the quadratic law for generating the sequence,
with $d = pr$, $a = 1 + ps$, yields
$Z↓{n+1} ≡ 2rtnc + st + Z↓n\modulo {p}$.
It follows that $Z↓{n+p} ≡ Z↓n \modulo {p}$; hence
$$X↓{n+kp↑f} ≡ X↓n + k(tp↑f + Z↓np↑{f+1})\quad \modulo
{p↑{f+2}}$$
for $k = 1, 2, 3, \ldotss$; setting $k = p$ completes
the proof.

{\sl Notes:} If $f(x)$ is a polynomial of degree
higher than 2 and $X↓{n+1} = f(X↓n)$, the analysis is more complicated,
although we can use the fact that $f(m + p↑k) = f(m) + p↑kf↑\prime
(m) + p↑{2k}f↑{\prime\prime} (m)/2! + \cdots$ to prove that many polynomial
recurrences give the maximum period. For example, \α{Coveyou} has
proved that the period is $m = 2↑e$ if $f(0)$ is odd, $f↑\prime
(j) ≡ 1$, $f↑{\prime\prime}(j) ≡ 0$, and $f(j + 1) ≡ f(j) + 1 \modulo
{4}$ for $j = 0, 1, 2, 3$.\xskip [{\sl Studies in Applied Math.\ \bf 3} (1967),
70--111.]

\ansno 9. Let $X↓n = 4Y↓n + 2$; then the
sequence $Y↓n$ satisfies the quadratic recurrence $Y↓{n+1} =
(4Y↑{2}↓{n} + 5Y↓n + 1)\mod 2↑{e-2}$.

\ansno 10.  {\sl Case 1:} $X↓0 = 0$, $X↓1 = 1$; hence $X↓n
≡ F↓n$. We seek the smallest $n$ for which $F↓n ≡ 0$ and $F↓{n+1}
≡ 1\modulo {2↑e}$. Since $F↓{2n} = F↓n(F↓{n-1} + F↓{n+1})$, $F↓{2n+1}
= F↑{2}↓{n} + F↑{2}↓{n+1}$, we find by induction on $e$ that,
for $e > 1$, $F↓{3\cdot2↑{e-1}}≡0$ and $F↓{3\cdot2↑{e-1}+1}≡2↑e+1
\modulo{2↑{e+1}}$.
This implies that the period is a divisor of $3 \cdot 2↑{e-1}$
but not a divisor of $3 \cdot 2↑{e-2}$, so it is either $3 \cdot 2↑{e-1}$
or $2↑{e-1}$. But $F↓{2↑{e-1}}$ is always
odd (since only $F↓{3n}$ is even).

{\sl Case 2:} $X↓0 = a$, $X↓1 = b$. Then
$X↓n ≡ aF↓{n-1} + bF↓n$; we need to find the smallest positive
$n$ with $a(F↓{n+1} - F↓n) + bF↓n ≡ a$ and $aF↓n + bF↓{n+1} ≡ b$.
This implies that $(b↑2 - ab - a↑2)F↓n ≡ 0$, $(b↑2 - ab - a↑2)(F↓{n+1}
- 1) ≡ 0$; and $b↑2 - ab - a↑2$ is odd (i.e., prime to $m$)
so the condition is equivalent to $F↓n ≡ 0$, $F↓{n+1} ≡ 1$.

Methods to determine the period of $F↓n$
for any modulus appear in an article by D.↔D. \α{Wall,} {\sl AMM
\bf 67} (1960), 525--532. Further facts about the Fibonacci
sequence mod $2↑e$ have been derived by B. \α{Jansson} [{\sl Random
Number Generators} (Stockholm: Almqvist & Wiksell, 1966),
Section 3C1].

\def\\#1{\penalty0\;\biglp\hbox{modulo }f(z)\hbox{ and }#1\bigrp}
\ansno 11. (a)\9 We have $z↑λ = 1 + f(z)u(z) + p↑ev(z)$
for some $u(z), v(z)$, where $v(z) \neqv 0\\{p}$.
By the binomial theorem
$$z↑{λp} = 1 + p↑{e+1}v(z) + p↑{2e+1}v(z)↑2(p - 1)/2$$
plus further terms congruent to zero $\\{p↑{e+2}}$.
Since $p↑e>2$, we have $z↑{λp}≡1+p↑{e+1}v(z)\\{p↑{e+2}}$.
If $p↑{e+1}v(z) ≡ 0 \\{p↑{e+2}}$,
there must exist polynomials $a(z)$ and $b(z)$ such
that $p↑{e+1}\biglp v(z) + pa(z)\bigrp = f(z)b(z)$. Since $f(0)
= 1$, this implies that $b(z)$ is a multiple of $p↑{e+1}$ (by
Gauss's Lemma 4.6.1G); hence $v(z) ≡ 0\\{p}$,
a contradiction.

(b)\9 If $z↑λ - 1 = f(z)u(z) + p↑ev(z)$, then
$$G(z) = u(z)/(z↑λ - 1) + p↑ev(z)/f(z)(z↑λ - 1);$$
hence $A↓{n+λ} ≡ A↓n \modulo {p↑e}$ for large
$n$. Conversely, if $\langle A↓n\rangle$ has the latter property
then $G(z) = u(z) + v(z)/(1 - z↑λ) + p↑eH(z)$, for some polynomials
$u(z)$ and $v(z)$, and some power series $H(z)$, all with integer
coefficients. This implies the identity $1 - z↑λ = u(z)f(z)(1 - z↑λ)
+ v(z)f(z) + p↑eH(z)f(z)(1 - z↑λ)$; and $H(z)f(z)(1 - z↑λ)$
is a polynomial since the other terms of the equation are polynomials.

(c)\9 It suffices to prove that $λ(p↑e) ≠ λ(p↑{e+1})$
implies that $λ(p↑{e+1}) = pλ(p↑e) ≠ λ(p↑{e+2})$. Applying (a)
and (b), we know that $λ(p↑{e+2}) ≠ pλ(p↑e)$, and that $λ(p↑{e+1})$
is a divisor of $pλ(p↑e)$ but not of $λ(p↑e)$. Hence if $λ(p↑e)
= p↑fq$, where $q \mod p ≠ 0$, then $λ(p↑{e+1})$ must be $p↑{f+1}d$,
where $d$ is a divisor of $q$. But now $X↓{n+p↑{f+1}}
≡ X↓n \modulo {p↑e}$; hence $p↑{f+1}d$ is a multiple
of $p↑fq$, hence $d = q$.\xskip [{\sl Note:} The hypothesis $p↑e >2$
is necessary; for example, let $a↓1 = 4$, $a↓2 = -1$, $k = 2$; then
$\langle A↓n\rangle = 1$, 4, 15, 56, 209, 780, $\ldotss$; $λ(2)
= 2$, $λ(4) = 4$, $λ(8) = 4$.]

(d)\9 $g(z) = X↓0 + (X↓1 - a↓1X↓0)z + \cdots$\par
\rjustline{$+ (X↓{k-1} - a↓1X↓{k-2} - a↓2X↓{k-3} - \cdots
- a↓{k-1}X↓0)z↑{k-1}$.\quad}

(e)\9 The derivation in (b) can be generalized
to the case $G(z) = g(z)/f(z)$; then the assumption of period
length $λ$ implies that $g(z)(1 - z↑λ) ≡ 0 \\{p↑e}$;
we treated only the special case $g(z)
= 1$ above. But both sides of this congruence can be multiplied
by Hensel's $b(z)$, and we obtain $1 - z↑λ ≡ 0 \\{p↑e}$.

{\sl Note:} A more ``elementary'' proof of the
result in (c) can be given without using generating functions,
using methods analogous to those in the answer to exercise↔8:
If $A↓{λ+n} = A↓n + p↑eB↓n$, for $n = r, r + 1, \ldotss ,
r + k - 1$ and some integers $B↓n$, then this same relation
holds for {\sl all} $n ≥ r$ if we define $B↓{r+k}, B↓{r+k+1},
\ldots$ by the given recurrence relation. Since the resulting
sequence of $B$'s is some linear combination of shifts of the
sequence of $A$'s, we will have $B↓{λ+n} ≡ B↓n \modulo {p↑e}$
for all large enough values of↔$n$. Now $λ(p↑{e+1})$ must be
some multiple of $λ = λ(p↑e)$; for all large enough $n$ we have
$A↓{n+jλ} = A↓n + p↑e(B↓n + B↓{n+λ} + B↓{n+2λ} + \cdots
+ B↓{n+(j-1)λ}) ≡ A↓n + jp↑eB↓n \modulo {p↑{2e}}$ for
$j = 1, 2, 3, \ldotss\,.$ No $k$ consecutive $B$'s are multiples
of $p$; hence $λ(p↑{e+1}) = pλ(p↑e) ≠ λ(p↑{e+2})$ follows immediately
when $e ≥ 2$. We still must prove that $λ(p↑{e+2}) ≠ pλ(p↑e)$
when $p$ is odd and $e = 1$; here we let $B↓{λ+n} = B↓n +
pC↓n$, and observe that $C↓{n+λ} ≡ C↓n \modulo {p}$ when
$n$ is large enough. Then $A↓{n+p} ≡ A↓n + p↑2\left( B↓n + {p\choose 2}
C↓n\right)\modulo {p↑3}$, and the proof is readily completed.

For the history of this problem, see Morgan \α{Ward},
{\sl Trans. Amer. Math. Soc. \bf 35} (1933), 600--628; see
also D. W. \α{Robinson,} {\sl AMM \bf 73} (1966), 619--621.
% Vicinity of page 528
% folio 666 galley 5 	*
\ansno 12. The period length mod 2 can be
at most↔4; and the period length mod↔$2↑{e+1}$ is at
most twice the maximum length mod $2↑e$, by the considerations
of the previous exercise. So the maximum conceivable period
length is $2↑{e+1}$; this is achievable, for example, in the
trivial case $a = 0$, $b = c = 1$.

\ansnos 13,14.  Clearly $Z↓{n+λ} = Z↓n$, so $λ↑\prime$
is certainly a divisor of $λ$. Let the least common multiple
of $λ↑\prime$ and $λ↓1$ be $λ↑{\prime}↓{1}$, and define $λ↑{\prime}↓{2}$
similarly. $X↓n + Y↓n ≡ Z↓n ≡ Z↓{n+λ↓1↑\prime} ≡ X↓n +
Y↓{n+λ↓1↑\prime}$, so $λ↓1↑\prime$ is a multiple of $λ↓2$.
Similarly, $λ↑{\prime}↓{2}$
is a multiple of $λ↓1$. This yields the desired result.\xskip (The
result is ``best possible'' in the sense that sequences for
which $λ↑\prime = λ↓0$ can be constructed, as well as sequences
for which $λ↑\prime = λ$.)

\ansno 15.  Algorithm↔M generates $(X↓{n+k}, Y↓n)$ in
step M1 and outputs $Z↓n = X↓{n+k-q↓n}$ in step M3, for
all sufficiently large $n$. Thus $\langle Z↓n\rangle$ has a period of length
$λ↑\prime $, where $λ↑\prime$ is the least positive integer such
that $X↓{n+k-q↓n} = X↓{n+λ↑\prime+k-q↓{n+λ↑\prime}}$
for all large $n$. Since $λ$ is a
multiple of $λ↓1$ and $λ↓2$, it follows that $λ↑\prime$ is a
divisor of $λ$.\xskip (These observations are due to Alan G. \α{Waterman}.)

We also have $n + k - q↓n ≡ n + λ↑\prime + k -
q↓{n+λ↑\prime}\modulo {λ↓1}$ for all large $n$, by the distinctness
of the $X$'s. The bound on $\langle q↓n\rangle$ implies that
$q↓{n+λ↑\prime} = q↓n + c$ for all large $n$, where $c ≡ λ↑\prime
\modulo {λ↓1}$ and $\leftv c\rightv < {1\over 2}λ↓1$. But $c$ must be
0 since $\langle q↓n\rangle$ is bounded. Hence $λ↑\prime ≡ 0
\modulo {λ↓1}$, and $q↓{n+λ↑\prime}= q↓n$ for all large $n$;
it follows that $λ↑\prime$ is a multiple of $λ↓2$ and $λ↓1$,
so $λ↑\prime = λ$.

{\sl Note:} The answer to exercise 3.2.1.2--4
implies that when $\langle Y↓n\rangle$ is a linear congruential
sequence of maximum period modulo $m = 2↑e$, the period length
$λ↓2$ will be at most $2↑{e-2}$ when $k$ is a power of 2.

\ansno 16.  There are several methods of proof.

(1)\9 Using the theory of finite fields.\xskip
In the field with $2↑k$ elements let $\xi$ satisfy $\xi ↑k =
a↓1\xi ↑{k-1} + \cdots + a↓k$. Let $f(b↓1\xi ↑{k-1} + \cdots
+ b↓k) = b↓k$, where each $b↓j$ is either zero or one; this
is a linear function. If word \.X in the generation algorithm
is $(b↓1b↓2 \ldotsm b↓k)↓2$ before (10) is executed, and if $b↓1\xi
↑{k-1} + \cdots + b↓k\xi ↑0 = \xi ↑n$, then word \.X represents
$\xi ↑{n+1}$ after (10) is executed. Hence the sequence is $f(\xi
↑n)$, $f(\xi ↑{n+1})$, $f(\xi ↑{n+2})$, $\ldotss$; and $f(\xi ↑{n+k})
= f(\xi ↑n\xi ↑k) = f(a↓1\xi ↑{n+k-1} + \cdots + a↓k\xi ↑n)
= a↓1f(\xi ↑{n+k-1}) + \cdots + a↓kf(\xi ↑n)$.

(2)\9 Using brute force, or elementary ingenuity.\xskip
We are given a sequence $X↓{nj}$, $n ≥ 0$, $1 ≤ j ≤ k$, satisfying
$$X↓{(n+1)j} ≡ X↓{n(j+1)} + a↓jX↓{n1},\qquad 1 ≤ j < k;\qquad
X↓{(n+1)k} ≡ a↓kX↓{n1}\quad \modulo 2.$$
We must show that this implies $X↓{nk} ≡ a↓1X↓{(n-1)k}
+ \cdots + a↓kX↓{(n-k)k}$, for $n ≥ k$. Indeed, it implies
$X↓{nj} ≡ a↓1X↓{(n-1)j} + \cdots + a↓kX↓{(n-k)j}$ when $1 ≤
j ≤ k ≤ n$. This is clear for $j = 1$, since $X↓{n1} ≡ a↓1X↓{(n-1)1}
+ X↓{(n-1)2} ≡ a↓1X↓{(n-1)1} + a↓2X↓{(n-2)2} + X↓{(n-2)3}$,
etc. For $j > 1$, we have by induction
$$\eqalign{X↓{nj} ⊗≡ X↓{(n+1)(j-1)} - a↓{j-1}X↓{n1}\cr
\noalign{\vskip 6pt}
⊗≡ \sum ↓{1
≤i≤k} a↓iX↓{(n+1-i)(j-1)} - a↓{j-1} \sum ↓{1≤i≤k} a↓iX↓{(n-i)1}\cr
⊗≡ \sum ↓{1≤i≤k} a↓i(X↓{(n+1-i)(j-1)} - a↓{j-1}X↓{(n-i)1})\cr
⊗≡ a↓1X↓{(n-1)j} + \cdots + a↓kX↓{(n-k)j}.\cr}$$
This proof does {\sl not} depend on the fact that operations
were done modulo 2, or modulo any prime number.

\ansno 17.  (a)\9 When the sequence terminates, the $(k
- 1)$-tuple $(X↓{n+1}, \ldotss, X↓{n+k-1})$ occurs for the $(m
+ 1)$st time. A given $(k - 1)$-tuple $(X↓{r+1}, \ldotss, X↓{r+k-1})$
can have only $m$ distinct predecessors $X↓r$, so one of these
occurrences must be for $r = 0$.\xskip (b) Since the $(k - 1)$-tuple
$(0, \ldotss , 0)$ occurs $(m + 1)$ times, each possible predecessor
appears, so the $k$-tuple $(a↓1, 0, \ldotss , 0)$ appears for
all $a↓1, 0 ≤ a↓1 < m$. Let $1 ≤ s < k$ and suppose we have
proved that all $k$-tuples $(a↓1, \ldotss , a↓s, 0, \ldotss ,
0)$ appear in the sequence when $a↓s ≠ 0$. By the construction,
this $k$-tuple would not be in the sequence unless $(a↓1, \ldotss
, a↓s, 0, \ldotss , 0, y)$ had appeared earlier for $1 ≤ y <
m$. Hence the $(k - 1)$-tuple $(a↓1, \ldotss , a↓s, 0, \ldotss
, 0)$ has appeared $m$ times, and all $m$ possible predecessors
appear; this means $(a, a↓1, \ldotss , a↓s, 0, \ldotss , 0)$ appears
for $0 ≤ a < m$. The proof is now complete by induction.

The result also follows from Theorem 2.3.4.2D\null,
using the directed graph of exercise 2.3.4.2--23; the set of
arcs from $(x↓1, \ldotss , x↓j, 0, \ldotss , 0)$ to $(x↓2, \ldotss
, x↓j, 0, \ldotss , 0, 0)$, where $x↓j ≠ 0$ and $1 ≤ j ≤ k$,
forms an oriented subtree related neatly to \α{Dewey decimal notation}.

\ansno 18.  The third-most-significant bit of $U↓{n+1}$
is completely determined by the first and third bits of $U↓n$,
so only 32 of the 64 possible pairs $(\lfloor 8U↓n\rfloor ,
\lfloor 8U↓{n+1}\rfloor )$ occur.\xskip ({\sl Notes:} If we had
used, say, 11-bit numbers $U↓n = (.X↓{11n}X↓{11n+1} \ldotsm X↓{11n+10})↓2$,
the sequence {\sl would} be satisfactory for many applications.
If another constant appears in \.A having more ``one'' bits,
the generalized spectral test might give some indication of
its suitability. See exercise 3.3.4--24; we could examine $\nu
↓t$ in dimensions $t = 36, 37, 38, \ldotss\,$.)

\ansno 21. [{\sl J. London Math. Soc. \bf 21} (1946),
169--172.]\xskip Any sequence of period length $m↑k - 1$ with no $k$
consecutive zeros leads to a sequence of period length $m↑k$
by inserting a zero in the appropriate place, as in exercise↔7;
 conversely, we can start with a sequence of period length
$m↑k$ and delete an appropriate zero from the period, to form
a sequence of the other type. Let us call these ``$(m, k)$ sequences''
of types A and B. The hypothesis assures us of the existence
of $(p, k)$ sequences of type A, for all primes $p$ and all
$k ≥ 1$; hence we have $(p, k)$ sequences of type B for all
such $p$ and $k$.


To get a $(p↑e, k)$ sequence of type B, let
$e = qr$, where $q$ is a power of $p$ and $r$ is not a multiple
of $p$. Start with a $(p, qrk)$ sequence of type A, namely
$X↓0, X↓1, X↓2, \ldotss $; then (using the $p$-ary number system)
the grouped digits $(X↓0 \ldotsm X↓{q-1})↓p, (X↓q \ldotsm X↓{2q-1})↓p,
\ldots$ form a $(p↑q, rk)$ sequence of
type A, since $q$ is relatively prime to $p↑{qrk} - 1$ and
the sequence therefore has a period length of $p↑{qrk} - 1$.
This leads to a $(p↑q, rk)$ sequence $\langle Y↓n\rangle$ of
type B; and $(Y↓0Y↓1 \ldotsm Y↓{r-1})↓{p↑q}$, $(Y↓rY↓{r+1}
\ldotsm Y↓{2r-1})↓{p↑q}$, $\ldots$ is a $(p↑{qr}, k)$ sequence
of type B by a similar argument, since $r$ is relatively prime
to $p↑{qk}$.

To get an $(m, k)$ sequence of type B for arbitrary
$m$, we can combine $(p↑e, k)$ sequences for each of the prime
power factors of $m$ using the Chinese remainder theorem; but
a simpler method is available. Let $\langle X↓n\rangle$ be an
$(r, k)$ sequence of type↔B, and let $\langle Y↓n\rangle$
be an $(s, k)$ sequence of type B, where $r$ and $s$ are relatively
prime; then $\langle sX↓n + Y↓n\rangle$ is an $(rs, k)$ sequence
of type B.

A simple, uniform construction that yields $(2,
k)$ sequences for arbitrary $k$ has been discovered by A. \α{Lempel}
[{\sl IEEE Trans.\ \bf C--19} (1970), 1204--1209].

\ansno 22.  By the Chinese remainder theorem, we can find constants
$a↓1, \ldotss , a↓k$ having desired residues mod each prime
divisor of $m$. If $m = p↓1p↓2 \ldotsm p↓t$, the period
length will be lcm$(p↑{k}↓{1} - 1, \ldotss , p↑{k}↓{t}
- 1)$. In fact, we can achieve reasonably long periods for ar\-bi\-trary↔$m$
(not necessarily squarefree), as shown in exercise↔11.

\ansno 23.  Period length at least $2↑{55} - 1$; possibly
faster than (7), see exercise 3.2.1.1--5. Furthermore, R. \α{Brent}
has pointed out that the calculations can be done exactly on
floating point numbers in $[\,0, 1)$.

\ansno 24.  Run the sequence backwards. In other words, if $Z↓n
= Y↓{-n}$ we have $Z↓n = (Z↓{n-m+k} + Z↓{n-m})\mod 2$.

\ansno 25.  This actually would be slower and more complicated, unless it
can be used to save subroutine-calling overhead in high-level languages.\xskip
(See the {\:c FORTRAN} program in Section 3.6.)

\ansno 27. Let $J↓n=\lfloor k X↓n/m\rfloor$.\xskip {\sl Lemma:} After the
$(k↑2+7k-2)/2$ consecutive values
$$0↑{k+2}\ 1\ 0↑{k+1}\ 2\ 0↑k\ \ldots\ (k-1)\ 0↑3$$
occur in the $\langle J↓n \rangle$ sequence, Algorithm↔B will have $V[i]
< m/k$ for $0≤j<k$, and also $Y<m/k$.\xskip {\sl Proof.} Let $S↓n$ be the
set of positions $i$ such that $V[i]<m/k$ just before $X↓n$ is generated,
and let $j↓n$ be the index such that $V[j↓n]←X↓n$. If $j↓n \notin S↓n$ and
$J↓n=0$, then $S↓{n+1}=S↓n ∪ \{j↓n\}$; if $j↓n \in S↓n$ and $J↓n=0$, then
$S↓{n+1}=S↓n$ and $j↓{n+1}=0$. After $k+2$ successive 0's, we must therefore
have $0\in S↓n$ and $j↓{n+1}=0$. Then after ``$1\ 0↑{k+1}$'' we must have
$\{0,1\} \subset S↓n$ and $j↓{n+1}=0$; after ``$2\ 0↑k$'' we must have
$\{0,1,2\} \subset S↓n$ and $j↓{n+1}=0$; and so on.

{\sl Corollary:} For $λ≥2(k↑2+7k-2) k↑{(k↑2+7k-2)/2}$, either Algorithm↔B
yields a period of length $λ$ or the sequence $\langle X↓n\rangle$ is poorly
distributed.\xskip {\sl Proof.} The probability that
any given length-$l$ pattern of $J$'s does not occur in a random sequence of
length $λ$ is less than $(1-k↑{-l})↑{λ/l}<\exp(-k↑{-l}λ/l)$. For $l=(k↑2+7k-2)/2$
this is at most $e↑{-4}$; hence the stated pattern should appear. After it
does, the subsequent behavior of Algorithm↔B will be the same each time it
reaches this part of the period.

\ansbegin{3.3.1}

\def\splus{↑{\scriptscriptstyle+}}
\def\sminus{↑{\scriptscriptstyle-}}
\ansno 1. There are $k = 11$
categories, so the line $\nu = 10$ should be used.

\ansno 2.  ${2\over 49}$, ${3\over 49}$, ${4\over 49}$,
${5\over 49}$, ${6\over 49}$, ${9\over 49}$, ${6\over 49}$,
${5\over 49}$, ${4\over 49}$, ${3\over 49}$, ${2\over 49}$.

\ansno 3.  $V = 7{173\over 240}$, only very slightly higher
than that obtained from the good dice! There are two reasons
why we do not detect the weighting:\xskip (a) The new probabilities
(cf.\ exercise↔2) are not really very far from the old ones in
Eq.\ (1). The sum of the two dice tends to smooth out the probabilities;
if we considered instead each of the 36 possible pairs of values,
and counted these, we would probably detect the difference quite
rapidly (assuming that the two dice are distinguishable).\xskip (b) A far
more important reason is that $n$ is too small for a significant
difference to be detected. If the same experiment is done for
large enough $n$, the faulty dice will be discovered (see exercise↔12).

\ansno 4.  $p↓s = {1\over 12}$ for $2 ≤ s ≤ 12$ and $s
≠ 7$; $p↓7 = {1\over 6}$. The value of $V$ is 16${1\over 2}$,
which falls between the $75\%$ and $95\%$ entries in Table↔1;
so it is reasonable, in spite of the fact that not too
many sevens actually turned up.

\ansno 5.  $K\splus ↓{20} = 1.15; K\sminus ↓{20} = 0.215$; these
do not differ significantly from random behavior (being at about
the $94\%$ and $86\%$ levels), but they are mighty close.\xskip
(The data values in this exercise come from Appendix↔A, Table↔1.)

\ansno 6.  The probability that $X↓j ≤ x$ is $F(x)$, so
we have the binomial distribution
discussed in Section 1.2.10. $F↓n(x) = s/n$ with probability
${n\choose s}\,F(x)↑s\biglp 1 - F(x)\bigrp ↑{n-s}$;
the mean is $F(x)$; the standard deviation is $\sqrt{F(x)\biglp
1 - F(x)\bigrp /n}$.\xskip [Cf.\ Eq. 1.2.10--19. This suggests that
a slightly better statistic would be to define
$$K\splus ↓{n} = \sqrt n\max↓{-∞<x<∞}\biglp F↓n(x)
- F(x)\bigrp /\sqrt{F(x)\biglp 1 - F(x)\bigrp};$$
see exercise 22. We can calculate
the mean and standard deviation of $F↓n(x) - F↓n(y)$, for $x
< y$, and obtain the covariance of $F↓n(x), F↓n(y)$. Using these
facts, it can be shown that for large values of $n$ the function
$F↓n(x)$ behaves as a ``Brownian motion,'' and techniques from
this branch of probability theory may be used to study it. The
situation is exploited in articles by J. L. \α{Doob} and M. D. \α{Donsker},
{\sl Annals Math.\ Stat.\ \bf 20} (1949), 393--403
and {\bf 23} (1952), 277--281; this is generally regarded as the most
enlightening way to study the KS tests.]
% Vicinity of page 531
% folio 670 galley 6 	*
\ansno 7. $\biglp$(Cf.\ Eq.\ (13).$\bigrp$\xskip Take
$j = n$ to see that $K\splus ↓{n}$ is never negative and it can
get as high as $\sqrt{n}$. Similarly, take $j = 1$ to make the
same observations about $K\sminus ↓{n}$.

\ansno 8.  The new KS statistic was computed for 20 observations.
The distribution of $K\splus ↓{10}$ was used as $F(x)$ when the
KS statistic was computed.

\ansno 9.  The idea is erroneous, because all of the
observations must be {\sl \α{independent}.} There is a relation
between the statistics $K\splus ↓{n}$ and $K\sminus ↓{n}$ on the same
data, so each test should be judged separately.\xskip (A high value
of one tends to give a low value of the other.)\xskip Similarly, the
entries in Figs.\ 2 and↔5 (which show 15 tests for each generator)
do not show 15 independent observations, because the \hbox{maximum-of-5}
test is not independent of the \hbox{maximum-of-4} test.
The three tests of each horizontal row are independent (because
they were done on different parts of the sequence), but the
five tests in a column are somewhat correlated. The net effect
of this is that the 95-percent probability levels, etc., which
apply to one test, cannot legitimately be applied to a whole
group of tests on the same data. Moral: When testing a random number
generator, we may expect it to ``pass'' each of several tests,
e.g., the frequency test, maximum test, run test; but
an array of data from several different tests should not be
considered as a unit since the tests themselves may not be independent.
The $K\splus ↓{n}$ and $K\sminus ↓{n}$ statistics should be considered
as two separate tests; a good source of random numbers will
pass both of the tests.

\ansno 10.  Each $Y↓s$ is doubled, and $np↓s$ is doubled,
so the numerators of (6) are quadrupled while the denominators
only double. Hence the new value of $V$ is twice as high as
the old one.

\ansno 11.  The empirical distribution function stays
the same; the values of $K\splus ↓{n}$ and $K\sminus ↓{n}$ are multiplied
by $\sqrt{2}$.

\ansno 12.  Let $Z↓s = (Y↓s - nq↓s)/\sqrt{nq↓s}$. The
value of $V$ is $n$ times
$$\sum ↓{1≤s≤k}(q↓s - p↓s + \sqrt{q↓s/n}Z↓s)↑2/p↓s,$$
and the latter quantity stays bounded away from
zero as $n$ increases (since $Z↓sn↑{-1/4}$ is bounded
with probability 1). Hence the value of $V$ will increase to
a value that is extremely improbable under the $p↓s$ assumption.

For the KS test, let $F(x)$ be the assumed distribution,
$G(x)$ the actual distribution, and let $h = \max \left|G(x) - F(x)\right|$.
Take $n$ large enough so that $\left|F↓n(x)
- G(x)\right| > h/2$ occurs with very small probability; then
$\left|F↓n(x) - F(x)\right|$ will be
improbably high under the assumed distribution $F(x)$.

\ansno 13.  (The ``max'' notation should really be replaced
by ``sup'' since a least upper bound is meant; however, ``max''
was used in the text to avoid confusing too many readers by
the less familiar ``sup'' notation.)\xskip For convenience, let $X↓0
= -∞$, $X↓{n+1} = +∞$. When $X↓j ≤ x < X↓{j+1}$, we have $F↓n(x)
= j/n$; therefore ${\max\biglp F↓n(x) - F(x)\bigrp}
= {j/n - F(X↓j)}$ and ${\max\biglp F(x) - F↓n(x)\bigrp} = {F(X↓{j+1})
- j/n}$ in this interval. As $j$ varies from 0 to↔$n$,
all real values of $x$ are considered; this proves that
$$\eqalign{
K\splus ↓{n}⊗=\sqrt n \max↓{0≤j≤n}\left({j\over n} - F(X↓j)\right);\cr
K\sminus ↓{n}⊗=\sqrt n \max↓{1≤j≤n+1}\left(F(X↓j) - {j - 1\over n}\right).\cr}$$
These are equivalent to (13), since the extra term under
the maximum signs is nonpositive and it must be redundant by
exercise↔7.

\ansno 14.  The logarithm of the left-hand side simplifies
to
$$\halign{\hbox to size{#}\cr
$\dispstyle-\!\sum ↓{1≤s≤k}Y↓s \ln\bigglp1 + {Z↓s\over
\sqrt{np↓s}}\biggrp + {1 - k\over 2}\ln(2πn)$\hfill\cr
\hfill$\dispstyle - {1\over 2}\sum ↓{1≤s≤k}\ln p↓s - {1\over 2}
\sum ↓{1≤s≤k}\ln\bigglp1 + {Z↓s\over \sqrt{np↓s}}\biggrp+O\left(1\over n\right),$\cr
}$$
and this quantity simplifies further (upon expanding $\ln(1
+Z↓s/\sqrt{np↓s})$ and realizing that $\sum ↓{1≤s≤k}
Z↓s\sqrt{np↓s} = 0$) to
$$-{1\over 2} \sum ↓{1≤s≤k} Z↑{2}↓{s} + {1 - k\over 2}
\ln(2πn) - {1\over 2} \ln(p↓1 \ldotsm p↓k) + O\bigglp{1\over
\sqrt{n}}\biggrp.$$

\ansno 15. The corresponding Jacobian determinant
is easily evaluated by (a) removing the factor $r↑{n-1}$ from
the determinant, (b) expanding the resulting determinant by
the cofactors of the row containing ``$\cos \theta ↓1$ $- \sin
\theta ↓1$ $0 \ldotsm 0$'' (each of the cofactor determinants
may be evaluated by induction), and (c) recalling that $\sin↑2
\theta ↓1 + \cos↑2 \theta ↓1 = 1$.

\vskip 4pt
\ansno 16. $\dispstyle \int ↑{z\sqrt{2x}+y}↓{0}\hskip-3.5pt\exp\left(- {u↑2\over 2x}
+\cdots\right)\,du = ye↑{-z↑2} + O\left(1\over
\sqrt{x}\right) + \int ↑{z\sqrt{2x}}↓{0}\hskip-4pt\exp\left(-{u↑2\over
2x}+\cdots\right)\,du.$

\vskip 11pt plus 3pt minus 8pt
\noindent The latter integral is
$$\int ↑{z\sqrt{2x}}↓{0}e↑{-u↑2/2x}\,du + {1\over 3x↑2} \int
↑{z\sqrt{2x}}↓{0}e↑{-u↑2/2x}u↑3\,du + O\bigglp{1\over
\sqrt{x}}\biggrp.$$
When all is put together, the final result is
$${\gamma (x + 1, x + z\sqrt{2x} + y)\over\Gamma
(x + 1)} = {1\over \sqrt{2π}} \int ↑{z\sqrt2}↓{-∞}e↑{-u↑2/2}
\,du + {e↑{-z↑2}\over\sqrt{2πx}}{\textstyle(y
- {2\over 3} - {2\over 3}z↑2)} + O\left(1\over x\right).$$
If we set $z\sqrt{2} = x↓p$ and write
$${1\over \sqrt{2π}} \int ↑{z\sqrt2}↓{-∞}e↑{-u↑2/2}
\,du = p,\qquad x + 1 = {\nu \over 2} ,\qquad \gamma \left({\nu
\over 2} , {t\over 2}\right)\left/\Gamma \left(\nu \over 2\right)\right.
= p,$$
where $t/2 = x + z\sqrt{2x} + y$, we can solve
for $y$ to obtain $y = {2\over 3}(1 + z↑2) + O(1/\sqrt{x}\,)$,
which is consistent with the above analysis. The solution is
therefore $t = \nu + 2\sqrt{\nu }z + {4\over 3}z↑2 - {2\over
3} + O(1/\sqrt{\nu }\,)$.

\ansno 17.  (a)\9 Change of variable, $x↓j ← x↓j + t$.\xskip (b)
Induction on $n$; by definition,
$$P↓{n0}(x - t) = \int ↑{x}↓{n}P↓{(n-1)0}(x↓n - t)\,dx↓n.$$
(c)\9 The left-hand side is
$$\int ↑{x+t}↓{n}\,dx↓n\; \ldots \int ↑{x↓{k+2}}↓{k+1}\,dx↓{k+1}\qquad
\hbox{times}\qquad \int ↑{k}↓{t}\,dx↓k \int ↑{x↓k}↓{t}\,dx↓{k-1}\; \ldots
\int ↑{x↓2}↓{t}\,dx↓1.$$
(d)\9 From (b), (c) we have
$$P↓{nk}(x) = \sum ↓{0≤r≤k} {(r - t)↑r\over r!} {(x + t - r)↑{n-r-1}\over
(n - r)!} (x + t - n).$$
The numerator in (24) is $P↓{n\lfloor t\rfloor}(n)$.

\ansno 18.  We may assume that $F(x) = x$ for $0 ≤ x ≤
1$, as remarked in the text's derivation of (24). If $0 ≤ X↓1
≤ \cdots ≤ X↓n ≤ 1$, let $Z↓j = 1 - X↓{n+1-j}$. We have $0
≤ Z↓1 ≤ \cdots ≤ Z↓n ≤ 1$; and $K\splus ↓{n}$ evaluated for $X↓1,
\ldots , X↓n$ equals $K\sminus ↓{n}$ evaluated for $Z↓1, \ldots
, Z↓n$. This symmetrical relation gives a one-to-one correspondence
between sets of equal volume for which $K\splus ↓{n}$ and $K\sminus ↓{n}$
fall in a given range.

\ansno 23. Let $m$ be any number $≥n$.\xskip (a)
If $\lfloor mF(X↓i)\rfloor = \lfloor mF(X↓j)\rfloor$ and $i
> j$, then $i/n - F(X↓i) > j/n - F(X↓j)$.\xskip (b) Start with $a↓k
= 1.0$, $b↓k = 0.0$, and $c↓k = 0$ for ${0 ≤ k < m}$. Then do the following for
each observation $X↓j$: Set $Y ← F(X↓j)$, $k ← \lfloor mY\rfloor$,
$a↓k ← \min(a↓k, Y)$, $b↓k ← \max(b↓k, Y)$, $c↓k ← c↓k + 1$.\xskip$\biglp$Assume
that $F(X↓j) < 1$ so that $k < m$.$\bigrp$\xskip Then set $j ← 0$, $r\splus  ← r\sminus 
← 0$, and for $k = 0$, 1, $\ldotss$, $m - 1$ (in this order) do
the following whenever $c↓k > 0$: Set $r\sminus  ← \max(r\sminus , a↓k
- j/n)$, $j ← j + c↓k$, $r\splus  ← \max(r\splus , j/n - b↓k)$. Finally set
$K\splus ↓{n} ← \sqrt{n}\,r\splus $, $K\sminus ↓{n} ← \sqrt{n}\,r\sminus $. The time
required is $O(m + n)$, and the precise value of $n$ need not
be known in advance.\xskip (If the estimate $(k + {1\over 2})/m$ is
used for $a↓k$ and $b↓k$, so that only the values $c↓k$ are actually
computed for each $k$, we obtain estimates of $K\splus ↓{n}$ and
$K\sminus ↓{n}$ good to within ${1\over2}\sqrt{n}/m$, even when $m < n$.)\xskip
[{\sl ACM Trans.\ Math.\ Software \bf 3} (1977), 60--64.]
% Vicinity of page 534
% folio 674 galley 7 	*
\ansbegin{3.3.2}

\ansno 1. The observations for
a chi-square test must be independent, and in the second sequence
successive observations are manifestly dependent, since the
second component of one equals the first component of the next.

\ansno 2.  Form $t$-tuples $(Y↓{jt}, \ldotss, Y↓{jt+t-1})$, for
$0 ≤ j < n$, and count how many of these equal each possible
value. Apply the chi-square test with $k = d↑t$ and with probability
$1/d↑t$ in each category. The number of observations, $n$, should
be at least $5d↑t$.

\ansno 3.  The probability that $j$ values are examined,
i.e., the probability that $U↓{j-1}$ is the $n$th element of
the sequence lying in the range $α ≤U↓{j-1} < β$, is easily
seen to be
$${j-1\choose n-1}\,p↑n(1 - p)↑{j-n},$$
by enumeration of the possible places in which
the other $n - 1$ occurrences can appear and by evaluating the
probability of such a pattern. The \α{generating function} is $G(z)
= \biglp pz/(1 - (1 - p)z)\bigrp ↑n$, which makes sense since
the given distribution is the $n$-fold convolution of the same
thing for $n = 1$. Hence the mean and variance are proportional
to $n$; the number of $U$'s to be examined is now easily found
to have the characteristics $\biglp$min\penalty200\ $n$, ave $n/p$, max $∞$,
dev $\sqrt{n(1 - p)}/p\bigrp$. A more detailed discussion of
this probability distribution when $n = 1$ may be found in the
answer to exercise 3.4.1--17; see also the considerably more
general results of exercise 2.3.4.2--26.

\ansno 4.  The probability of a gap of length $≥r$ is
the probability that $r$ consecutive $U$'s lie outside the given
range, i.e., $(1 - p)↑r$. The probability of a gap of length
exactly $r$ is the above value for length $≥r$ minus the value
for length $≥(r + 1)$.

\ansno 5.  As $N$ goes to infinity, so does $n$ (with
probability 1), hence this test is just the same as the gap
test described in the text except for the length of the very
last gap. And the text's gap test certainly is asymptotic to
the chi-square distribution stated, since the length of each
gap is independent of the length of the others.\xskip [{\sl
Notes:} A quite complicated proof of this result by E. \α{Bofinger}
and V. J. \α{Bofinger} appears in {\sl Annals Math.\ Stat.\ 
\bf 32} (1961), 524--534. Their paper is noteworthy because
it discusses several interesting variations of the gap test;
they show, for example, that the quantity
$$\sum ↓{0≤r≤t} {\biglp Y↓r - (Np)p↓r\bigrp ↑2\over (Np)p↓r}$$
does {\sl not} approach a chi-square distribution,
although others had suggested this statistic as a ``stronger''
test because $Np$ is the expected value of $n$.]

\ansno 7.  5, 3, 5, 6, 5, 5, 4.

\ansno 8.  See exercise 10, with $w = d$.

\ansno 9.  (Change $d$ to $w$ in steps C1 and C4.)\xskip We have
$$\eqalign{p↓r⊗ = {d(d - 1)\ldotsm(d - w + 1)\over d↑r}{r-1\comb\{\}
 w - 1},\qquad \hbox{for }w ≤ r < t;\cr
\noalign{\vskip 3pt}
p↓t⊗= 1 - {d!\over d↑{t-1}}\left({1\over 0!}{t-1\comb\{\}
d} + \cdots + {1\over (d - w)!} {t-1\comb\{\}w}\right).\cr}$$

\ansno 10. As in exercise↔3, we really need consider
only the case $n = 1$. The generating function for the probability
that a coupon set has length $r$ is
$$G(z) = {d!\over (d - w)!} \sum ↓{r>0}{r-1\comb\{\} w-1}\left( z\over d\right)↑r
= z↑w\left(d-1\over d-z\right)\ldotsm\left(d-w+1\over d-(w-1)z\right)$$
by the previous exercise and Eq.\ 1.2.9--28. The mean and variance are readily
computed using Theorem 1.2.10A and exercise 3.4.1--17. We find
that
$$\eqalign{\hbox{mean}(G)⊗= w + \left({d\over d - 1} - 1\right)+\cdots+
\left({d\over d-w+1}-1\right)=d(H↓d-H↓{d-w})=\mu;\cr
\hbox{var}(G) ⊗= d↑2(H↑{(2)}↓{d} - H↑{(2)}↓{d-w})
- d(H↓d-H↓{d-w}) = \sigma ↑2.\cr}$$
The number of $U$'s examined, as the search for a coupon
set is repeated $n$ times, therefore has the characteristics
$\biglp$min $wn$, ave $\mu n$, max $∞$, dev $\sigma \sqrt{n}\bigrp$.

\def\0{\hbox to 7pt{}}
\def\\{\hbox to 7pt{\hfill\vrule height 9.944pt depth 3pt\hfill}}
\ansno 11.  \\1\\2\\9\08\05\03\\6\\7\00\\4\\.

\ansno 12.  {\bf Algorithm R} ({\sl Data for run test\/}){\bf.}

\algstep R1. [Initialize.] Set $j
← -1$, and set $\.{COUNT}[1] ← \.{COUNT}[2] ← \cdots ←
\.{COUNT}[6] ← 0$. Also set $U↓n ← U↓{n-1}$, for convenience in terminating the
algorithm.

\algstep R2. [Set $r$ zero.] Set $r ← 0$.

\algstep R3. [Is $U↓j < U↓{j+1}?]$
Increase $r$ and $j$ by 1. If $U↓j < U↓{j+1}$, repeat this step.

\algstep R4. [Record the length.] If $r ≥
6$, increase $\.{COUNT}[6]$ by one, otherwise increase $\.{COUNT}[r]$
by one.

\algstep R5. [Done?] If $j < n - 1$, return
to step R2.\quad\blackslug

\def\\{\mathrel{\vcenter{\hbox{>}\vskip-4pt\hbox{<}}}}
\ansno 13. There are $(p +
q + 1){p+q\choose p}$ ways to have $U↓{i-1} \\ U↓i < \cdots
< U↓{i+p-1}\\ U↓{i+p} < \cdots < U↓{i+p+q-1}$; subtract
$p+q+1\choose p+1$ of these in which $U↓{i-1} < U↓i$, and
subtract $p+q+1\choose 1$ for those in which $U↓{i+p-1} <
U↓{i+p}$; then add in 1 for the case that both $U↓{i-1} < U↓i$
and $U↓{i+p-1} < U↓{i+p}$, since this case has been subtracted
out twice.\xskip (This is a special case of the \α{``inclusion-exclusion''
principle}, which is explained further in Section 1.3.3.)

\ansno 14.  A run of length $r$ occurs with probability
$1/r! - 1/(r + 1)!$, assuming distinct $U$'s.

\ansno 15.  This is always true of $F(X)$ when $F$ is
continuous and $S$ has distribution $F;$ see Section 3.3.1C.

\ansno 16.  (a)\9 $Z↓{jt} = \max(Z↓{j(t-1)}, Z↓{(j+1)(t-1)})$.
If the $Z↓{j(t-1)}$ are stored in memory, it is therefore a
simple matter to transform this array into the set of $Z↓{jt}$
with no auxiliary storage required.\xskip (b) With his ``improvement,''
each of the $V$'s should indeed have the stated distribution,
but the observations are no longer independent. In fact, when
$U↓j$ is a relatively large value, all of $Z↓{jt}$, $Z↓{(j-1)t}$,
$\ldotss$, $Z↓{(j-t+1)t}$ will be equal to $U↓j$; so we almost
have the effect of repeating the same data $t$ times (and that
would multiply $V$ by $t$, cf.\ exercise 3.3.1--10).

\ansno 17.  (b) By Lagrange's identity, the difference
\inx{Lagrange's identity: $whatever$}
is $\sum ↓{0≤k<j<n}(U↑{\prime}↓{\!k}V↑{\prime}↓{\!j}
- U↑{\prime}↓{\!j}V↑{\prime}↓{\!k})↑2$, and this is certainly positive.\xskip
(c) Therefore if $D↑2 = N↑2$, we must have $U↑{\prime}↓{\!k}V↑{\prime}↓{\!j}
- U↑{\prime}↓{\!j}V↑{\prime}↓{\!k} = 0$, for all pairs $j, k$. This
means that the matrix
$$\left(\vcenter{\halign{\ctr{$#↑\prime↓{\!1}$}⊗ \ctr{$#↑\prime↓{\!2}$}$\ldotsm$⊗\ctr
{$#↑\prime↓{\!n-1}$}\cr
U⊗U⊗U\cr V⊗V⊗V\cr}}\right)$$
has rank $<2$, so its rows are linearly dependent.\xskip
(A more elementary proof can be given, using the fact that $U↑\prime↓{\!0}V↑\prime↓{\!j}
- U↑{\prime}↓{\!j}V↑{\prime}↓{\!0} = 0$ for $ 1 ≤ j < n$ implies the
existence of constants $α, β$ such that $αU↑{\prime}↓{\!j} + βV↑{\prime}↓{\!j}
= 0$ for all $j$, provided that $U↑{\prime}↓{\!0}$ and $V↑{\prime}↓{\!0}$
are not both zero; the latter case can be avoided by a suitable
renumbering.)

\ansno 18.  (a)\9 The numerator is $-(U↓0 - U↓1)↑2$, the
denominator is $(U↓0 - U↓1)↑2$.\xskip (b) The nu\-mer\-a\-tor in this case is $-(U↑{2}↓{0}
+ U↑{2}↓{1} + U↑{2}↓{2} - U↓0U↓1 - U↓1U↓2 - U↓2U↓0)$; the de\-nom\-ina\-tor
is $2(U↑{2}↓{0} + \cdots - U↓2U↓0)$.\xskip (c) The denominator always
equals $\sum ↓{0≤j<k<n}(U↓j - U↓k)↑2$, by exercise
1.2.3--30 or 1.2.3--31.

\ansno 21. The successive values of $c↓{r-1}=s-1$ in step P2 are
2, 3, 7, 6, 4, 2, 2, 1, 0; hence $f=886862$.

\ansno 22.  $1024=6!+2\cdot5!+2\cdot4!+2\cdot3!+2\cdot2!+0\cdot1!$, so we
want the successive values of $s-1$ in step P2 to be 0, 0, 0, 1, 2, 2, 2, 2, 0;
working backwards, the permutation is $(9,6,5,2,3,4,0,1,7,8)$.

\ansbegin{3.3.3}

\ansno 1. $y((x/y))
+ {1\over 2}y - {1\over 2}y\delta (x/y)$.

\ansno 2. See exercises 1.2.4--38 and 1.2.4--39(a), (b), (g).

\ansno 3.  $f(x) = \sum ↓{n≥1}(-\sin 2πnx)/n$, which
converges for all $x$.\xskip (The representation in Eq.\ (24) may be
considered a ``finite'' Fourier series, for the case when $x$
is rational.)

\ansno 4.  $d = 2↑{10}\cdot 5$. Note that we have $X↓{n+1}
< X↓n$ with probability ${1\over 2} + \epsilon $, where
$$|\epsilon | < d/(2\cdot10↑{10}) = 1/(2\cdot5↑9);$$
hence {\sl every} potency-10 generator is respectable
from the standpoint of Theorem↔P.

\ansno 5.  An intermediate result:
$$\sum ↓{0≤x<m} {x\over m} {s(x)\over m} = {1\over 12} \sigma
(a, m, c) + {m\over 4} - {c\over 2m} - {x↑\prime \over 2m}.$$
% Vicinity of page 537
% folio 678 galley 8 (not on paper tape) 	*
\ansno 6. (a)\9 Use induction and the formula
$$\left(\!\left(hj+c\over k\right)\!\right)-\left(\!\left(hj+c-1\over k\right)\!\right)
={1\over k}-{1\over 2}\delta\left(hj+c\over k\right)-{1\over2}\delta\left(
hj+c-1\over k\right).$$
(b) Use the fact that $\dispstyle-\left(\!\left(h↑\prime j\over k\right)\!\right)
=-\left(\!\left({j\over hk}-{k↑\prime j\over h}\right)\!\right)=
\left(\!\left(k↑\prime j\over h\right)\!\right)-{j\over hk} + {1\over2}\delta
\left(k↑\prime j\over h\right)$.

\vskip 6pt
\ansno 7. Take $m=h$, $n=k$, $k=2$ in the second formula of exercise 1.2.4--45:
$$\twoline{\sum↓{0<j<k}\biggglp\hskip-2pt 
{hj\over k}-\left(\!\left(hj\over k\right)\!\right)+
{1\over 2}\hskip-2pt\bigggrp
\biggglp\hskip-2pt {hj\over k}-\left(\!\left(hj\over k\right)\!\right)-
{1\over 2}\hskip-2pt\bigggrp+2\!\<\sum↓{0<j<h}
\biggglp\hskip-2pt {kj\over h}-\left(\!\left(kj\over h\right)\!
\right)+{1\over 2}\hskip-2pt\bigggrp j}{2pt}{=kh(h-1).\hskip-9pt}$$
The sums on the left simplify, and by standard manipulations we get
$$h↑2k-hk-{h\over2}+{h↑2\over6k}+{k\over12}+{1\over4}-{h\over6}\sigma(h,k,0)
-{h\over6}\sigma(k,h,0)+{1\over12}\sigma(1,k,0)=h↑2k-hk.$$
Since $\sigma(1,k,0)=(k-1)(k-2)/k$, this reduces to the reciprocity law.

\ansno 8. See {\sl Duke Math.\ J. \bf21} (1954), 391--397.

\ansno 9. Begin with the handy identity $\sum↓{0≤k<r}\lfloor kp/r\rfloor\lfloor kq/r
\rfloor+\sum↓{0≤k<p}\lfloor kq/p\rfloor\lfloor kr/p\rfloor+\sum↓{0≤k<q}
\lfloor kr/q\rfloor\lfloor kp/q\rfloor = (p-1)(q-1)(r-1)$ for which a simple
geometric proof is possible.\xskip [U. Dieter, {\sl Abh.\ Math.\ Sem.\ Univ.\ 
Hamburg \bf21} (1957), 109--125.]

\ansno 10. Obviously $\sigma(k-h,k,c)=-\sigma(h,k,-c)$, cf.\ (8). Replace $j$
by $k-j$ in definition (16), to deduce that $\sigma(h,k,c)=\sigma(h,k,-c)$.

\vskip 6pt plus 3pt minus 2pt
\ansno 11. (a)\9$\dispstyle\sum↓{0≤j<dk}\left(\!\left(j\over dk\right)\!\right)\left(
\!\left(hj+c\over k\right)\!\right)=\sum↓{\scriptstyle 0≤i<d\atop\scriptstyle 0≤j<k}
\left(\!\left(ik+j\over dk\right)\!\right)\left(\!\left(hj+c\over k\right)\!\right)$;
use (10) to sum on $i$.\xskip (b) $\dispstyle\left(\!\left(hj+c+\theta\over k\right)
\!\right)=\left(\!\left(hj+c\over k\right)\!\right)+{\theta\over k}-{1\over2}\delta
\left(hj+c\over k\right)$; now sum.

\vskip 6pt plus 3pt minus 2pt
\ansno 12. Since $\biglp \biglp{hj+c\over k}\bigrp \bigrp $ runs through the same
values as $\biglp\biglp{ j\over k}\bigrp \bigrp $ in some order, Cauchy's
inequality implies that $\sigma(h,k,c)↑2≤\sigma(h,k,0)↑2$; and $\sigma(1,k,0)$
may be summed directly, cf.\ exercise↔7.

\ansno 13. $\dispstyle\sigma(h,k,c)+{3(k-1)\over k}={12\over k}\sum↓{0<j<k}
{\omega↑{-cj}\over(\omega↑{-hj}-1)(\omega↑j-1)}+{6\over k}(c\mod k)
-6\left(\!\left(h↑\prime c\over k\right)
\!\right)$,\par\noindent if $hh↑\prime≡1\modulo k$.

\ansno 14. $(2↑{38}-3\cdot2↑{20}+5)/(2↑{70}-1)\approx2↑{-32}$. An extremely
satisfactory global value, in spite of the local nonrandomness!

\ansno 15. Replace $c↑2$ where it appears in (19) by $\lfloor c\rfloor\lceil
c\rceil$.

\ansno 16. The hinted identity is equivalent to $m↓1=p↓rm↓{r+1}+p↓{r-1}m↓{r+2}$
for $1≤r≤t$; this follows by induction, cf.\ also exercise 4.5.3--32. Now
replace $c↓j$ by $\sum↓{j≤r≤t}b↓rm↓{r+1}$ and compare coefficients of $b↓ib↓j$
on both sides of the identity to be proved.

{\sl Note:} For all exponents $e≥1$ we have
$$\sum↓{1≤j≤t}(-1)↑{j+1}{c↑e↓j\over m↓jm↓{j+1}}={1\over m↓1}\sum↓{1≤j≤t}
(-1)↑{j+1}b↓j{(c↑e↓j-c↑e↓{j+1})\over c↓j-c↓{j+1}}p↓{j-1}$$
by a similar argument.

\ansno 17. During this algorithm we will have $k=m↓j$, $h=m↓{j+1}$, $c=c↓j$,
$p=p↓j-1$, $p↑\prime=p↓{j-2}$, $s=(-1)↑{j+1}$ for $j=1$, 2, $\ldotss$, $t+1$.

\algstep D1. [Initialize.] Set $A←0$, $B←h$, $p←1$, $p↑\prime
←0$, $s←1$.

\algstep D2. [Divide.] Set $a←\lfloor k/h\rfloor$, $b←\lfloor c/h\rfloor$,
$r←c\mod h$.\xskip (Now $a=a↓j$, $b=b↓j$, and $r=c↓{j+1}$.)

\algstep D3. [Accumulate.] Set $A←A-(a-6b)s$, $B←B+6bp(c+r)s$. If $r≠0$ or
$c=0$, set $A←A-3s$. If $h=1$, set $B←B+ps$.\xskip (This subtracts $3e(m↓{j+1},c↓j)$
and also takes care of the $\sum(-1)↑{j+1}/m↓jm↓{j+1}$ terms.)

\algstep D4. [Prepare for next iteration.] Set $c←r$, $s←-s$; set $r←k-ah$,
$k←h$, $h←r$; set $r←ap+p↑\prime$, $p↑\prime←p$, $p←r$. If $h>0$, return to
D2.\quad\blackslug

\penalty-400 % good place to break (January 1979)
\yyskip At the conclusion of this algorithm, $p$ will be equal to the original value
$k↓0$ of $k$, so the desired answer will be $A+B/p$. The final value of $p↑\prime$
will be $h↑\prime$ if $s<0$, otherwise $p↑\prime$ will be $k↓0-h↑\prime$.
It would be possible to
maintain $B$ in the range $0≤B<k↓0$, by making appropriate adjustments to
$A$, thereby requiring only single-precision operations (with double-precision
products and dividends) if $k↓0$ is a single-precision number.

\ansno 18. A moment's thought shows that the formula
$$\textstyle S(h,k,c,z)=\sum↓{0≤j<k}
\biglp\lfloor j/k\rfloor-\lfloor(j-z)/k\rfloor\bigrp\,\biglp\biglp(hj+c)/k\bigrp
\bigrp$$ is in fact valid for all $z$, not only when $k≥z$. Writing
$\lfloor j/k\rfloor-\lfloor(j-z)/k\rfloor={z\over k}+\biglp \biglp{j-z\over k}\bigrp 
\bigrp -\biglp \biglp{j\over k}\bigrp \bigrp +{1\over2}\delta↓{j0}-{1\over2}\delta
\biglp{j-z\over k}\bigrp $
and carrying out the sums yields $S(h,k,c,z)=zd((c/d))/k+{1\over12}\sigma(h,k,hz+c)
-{1\over12}\sigma(h,k,c)+{1\over2}((c/k))-{1\over2}\biglp\biglp(hz+c)/k\bigrp
\bigrp$, where $d=\gcd(h,k)$.
[This formula allows us to express the probability that
$X↓{n+1}<X↓n<α$ in terms of generalized Dedekind sums, given $α$.]

\ansno 19. The desired probability is
$$
\def\\{\lower 1.36pt\nullα} % makes α have an effective tail like β
\baselineskip 14pt\lineskip 3pt
\halign{\hbox to size{$\textstyle#$\hfill}\cr
\sum↓{0≤x<m}\biglp\lfloor(x-α)/m\rfloor-
\lfloor(x-β)/m\rfloor\bigrp\biglp\lfloor(s(x)-α↑\prime)/m\rfloor-
\lfloor(s(x)-β↑\prime)/m\rfloor\bigrp/m\cr
\noalign{\vskip4pt}
\def\biglp{\mathopen{\vcenter{\hbox{\:@\char0}}}}
\def\bigrp{\mathclose{\vcenter{\hbox{\:@\char1}}}}
\quad=\sum↓{0≤x<m}\left({β-α\over m}+\biglp\biglp{x-β\over m}
\bigrp\bigrp-\biglp\biglp{x-\\\over m}\bigrp\bigrp+{1\over2}\delta\biglp{ x-\\
\over m}\bigrp-{1\over2}\delta\biglp{x-β\over m}\bigrp\right)\cr
\noalign{\penalty1000}
\def\biglp{\mathopen{\vcenter{\hbox{\:@\char0}}}}
\def\bigrp{\mathclose{\vcenter{\hbox{\:@\char1}}}}
\quad\qquad
\null\times
\biglp{β↑\prime-α↑\prime\over m}+\biglp\biglp{ax+c-β↑\prime\over m}\bigrp \bigrp 
-\biglp\biglp{ax+c-\\↑\prime\over m}\bigrp \bigrp +{1\over2}\delta\biglp
{ax+c-\\↑\prime\over m}\bigrp -{1\over 2}\delta\biglp{ax+c-β↑\prime\over m}\bigrp 
\bigrp /m\cr
\noalign{\vskip4pt}
\quad={β-α\over m}{β↑\prime-α↑\prime\over m}+{1\over12m}
\biglp\sigma(a,m,c+aα-α↑\prime)-\sigma(a,m,c+aα-β↑\prime)\cr
\noalign{\penalty1000}
\hskip 120pt\null+\sigma(a,m,c+aβ-β↑\prime)
-\sigma(a,m,c+aβ-α↑\prime)\bigrp+ε,\cr}$$
where $|ε|≤2.5/m$.

[This approach is
due to U. Dieter. The discrepancy between the true probability and the
ideal value ${β-α\over m}{β↑\prime-α↑\prime\over m}$ is
bounded by $\sum↓{1≤j≤t}a↓j/4m$, according to Theorem↔K\null; conversely, by
choosing $α$, $β$, $α↑\prime$, $β↑\prime$ appropriately we will obtain a
discrepancy of at least half this bound when there are large partial quotients,
by the fact that Theorem↔K is ``best possible.'' Note that when $a
\approx \sqrt m$ the discrepancy cannot exceed $O\biglp1/\sqrt m\,\bigrp$, so
even the locally nonrandom generator of exercise↔14 will look good on the
serial test over the full period; it appears that we should insist on an
{\sl extremely} small discrepancy.]

\ansno 20. $\sum↓{0≤x<m}\left.\left\lceil\biglp x-s(x)\bigrp/m\right\rceil
\left\lceil\biglp s(x)-s(s(x))\bigrp/m\right\rceil\right/m
\hskip0ptplus3pt=\hskip0ptplus3pt
\sum↓{0≤x<m}\biglp\biglp x-s(x)\bigrp/m+\biglp\biglp(bx+c)/m\bigrp\bigrp+{1\over2}
\bigrp\biglp\biglp s(x)-s(s(x))\bigrp/m+\biglp\biglp a(bx+c)/m\bigrp\bigrp
+{1\over2}\bigrp\hbox{\:a/}m$; and $x/m=((x/m))+{1\over2}-{1\over2}\delta(x/m)$,
$s(x)/m=\biglp\biglp(ax+c)/m\bigrp\bigrp+{1\over2}-{1\over2}\delta\biglp(ax+c)
/m\bigrp$, $s(s(x))/m=\biglp\biglp(a↑2x+ac+c)/m\bigrp\bigrp+{1\over2}-{1\over2}
\delta\biglp(a↑2x+ac+c)/m\bigrp$. Let $s(x↑\prime)=s(x↑{\prime\prime})=0$ and
$d=\gcd(b,m)$. The sum now reduces to
$$\def\biglp{\mathopen{\vcenter{\hbox{\:@\char'20}}}}
\def\bigrp{\mathclose{\vcenter{\hbox{\:@\char'21}}}}
\twoline{{1\over4}+{1\over12m}(S↓1{-}S↓2{+}S↓3{-}S↓4{+}S↓5{-}S↓6{+}S↓7{-}S↓8{+}
S↓9)+
{d\over2m}\bigglp\!\left(\!\left(c\over d\right)\!\right){+}\left(\!\left(ac\over d\right)\!
\right)\!\biggrp}{2pt}{\null+{1\over2m}\bigglp\!\biglp\!\biglp{x↑\prime-x↑{\prime\prime}
\over m}\bigrp\!\bigrp{-}\biglp\!\biglp{x↑\prime\over m}\bigrp\!\bigrp{+}
\biglp\!\biglp{
x↑{\prime\prime}\over m}\bigrp\!\bigrp{+}\biglp\!\biglp{ac+c\over m}\bigrp\!\bigrp{-}
\biglp\!\biglp{ac\over m}\bigrp\!\bigrp{-}
\biglp\!\biglp{c\over m}\bigrp\!\bigrp{-}{1\over2}\!\biggrp,}$$
where $S↓1=\sigma(a,m,c)$, $S↓2=\sigma(a↑2,m,ac+c)$, $S↓3=\sigma(ab,m,ac)$,
$S↓4=\sigma(1,m,0)=({m-1})(m-2)/m$, $S↓5=\sigma(a,m,c)$, $S↓6=\sigma(b,m,c)$,
$S↓7=-\sigma(a↑\prime-1,m,a↑\prime c)$, and $S↓8=-\sigma(a↑\prime(a↑\prime-1),
m,(a↑\prime)↑2c)$, if $a↑\prime a≡1\modulo m$; and finally
$$\eqalign{S↓9⊗=12\sum↓{0≤x<m}\left(\!\left(bx+c\over m\right)\!\right)
\left(\!\left(a(bx+c)\over m\right)\!\right)\cr⊗=12d\sum↓{0≤x<m/d}\left(\!\left(x+c↓0/d
\over m/d\right)\!\right)\left(\!\left(a(x+c↓0/d\over m/d\right)\!\right)\cr
⊗=12d\sum↓{0≤x<m/d}\biggglp\left(\!\left(x\over m/d\right)\!\right)+
{c↓0\over m}-{1\over2}\delta↓{x0}\bigggrp\left(\!\left(a(x+c↓0/d)\over m/d
\right)\!\right)\cr
⊗=d\;\bigglp\sigma(ad,m,ac↓0)+12{c↓0\over m}\left(\!\left(ac↓0\over d\right)\!\right)
-6\left(\!\left(ac↓0\over m\right)\!\right)\biggrp\cr}$$
where $c↓0=c\mod d$. The grand total will be near $1\over6$ when $d$ is small
and when the fractions $a/m$, $(a↑2\mod m)/m$, $(ab\mod m)/m$, $b/m$, $(a↑\prime-1)
/m$, $(a↑\prime(a↑\prime-1)\mod m)/m$, $((ad)\mod m)/m$ all have small partial
quotients.\xskip (Note that $a↑\prime-1≡-b+b↑2-\cdotss$, cf.\ exercise 3.2.1.3--7.)

\ansno 21. $C=(s-({1\over2})↑2)/({1\over3}-({1\over2})↑2)$, where
$$\eqalign{s↓n⊗=\int↓{x↓n}↑{x↓{n+1}}x\{ax+\theta\}\,dx={1\over a↑2}\left(
{1\over3}-{\theta\over2}+{n\over 2}\right),\qquad
\hbox{if }x↓n={n-\theta\over a};\cr
s⊗=\int↓0↑1 x\{ax+\theta\}\,dx=s↓0+s↓1+\cdots+s↓{a-1}+\int↓{-\theta/a}↑0(ax+\theta)
\,dx\cr⊗={1\over3a}-{\theta\over2a}+{a-1\over4a}+{\theta↑2\over2a}.\cr}$$
Therefore $C=(1-6\theta+6\theta↑2)/a$.

\ansno 22. Let $[u,v)$ denote the set $\leftset x \relv u≤x<v\rightset$. We have
$s(x)<x$ in the disjoint intervals
$$\left[{1-\theta\over a},{1-\theta\over a-1}\right),\quad
\left[{2-\theta\over a},{2-\theta\over a-1}\right),\quad\ldotss,\quad
\left[{a-\theta\over a},1\right),$$
which have total length
$$1+\sum↓{0<j≤a-1}\left(j-\theta\over a-1\right)-\sum↓{0<j≤a}\left(j-\theta\over
a\right)=1+{a\over2}-\theta-{a+1\over2}+\theta={1\over2}.$$

\def\lrglb{\mathopen{\vcenter{\hbox{\:@\char2}}}}
\def\lrgrp{\mathclose{\vcenter{\hbox{\:@\char1}}}}
\save7\hbox{$\scriptstyle 1$}\def\strut{\vbox to 1ht7{}}
\ansno 23. We have $s(s(x))<s(x)<x$ when $x$ is in $\lrglb{k-\theta\over a\strut},
{k-\theta\over a-1}\lrgrp$ and $ax+\theta-k$ is in $\lrglb{j-\theta\over a\strut},
{j-\theta\over a-1}\lrgrp$, for $0<j≤k<a$; or when $x$ is in $\lrglb{a-\theta
\over a\strut},1\lrgrp$ and $ax+\theta-a$ is either in
$\lrglb{j-\theta\over a\strut},{j-\theta
\over a-1}\lrgrp$ for $0<j≤\lfloor a\theta\rfloor$ or in
$\lrglb{\lfloor a\theta\rfloor+1-\theta\over a},\theta\lrgrp$.
The desired probability is
$$\twoline{\sum↓{0<j≤k<a}{j-\theta\over a↑2(a-1)}+\sum↓{0<j≤\lfloor a\theta\rfloor}
{j-\theta\over a↑2(a-1)}+{1\over a↑2}\max(0,\{a\theta\}+\theta-1)}{3pt}{
={1\over6}+{1\over6a}-{\theta\over2a}+{1\over a↑2}\left({\lfloor a\theta\rfloor
(\lfloor a\theta\rfloor+1-2\theta)\over2(a-1)}+\max(0,\{a\theta\}+\theta-1)\right),
}$$ which is ${1\over6}+(1-3\theta+3\theta↑2)/6a+O(1/a↑2)$ for large $a$. Note
that $1-3\theta+3\theta↑2≥{1\over4}$, so $\theta$ can't be chosen to make this
probability come out right.
% Vicinity of page 540
% folio 687 galley 1 	*
\ansno 24. Proceed as in the previous exercise; the sum of the interval
lengths is
$$\sum↓{0<j↓1≤\cdots≤j↓{t-1}<a}\,{j↓1\over a↑{t-1}(a-1)}=
{1\over a↑{t-1}(a-1)}{a+t-2\choose t}.$$
To compute the average length, let $p↓k$ be the probability of a run of length
$≥k$; the average is
$$\sum↓{k≥1}p↓k=\sum↓{k≥1}{a+k-2\choose k}{1\over a↑{k-1}(a-1)}=\left(a\over
a-1\right)↑a-{a\over a-1}.$$
The value for a truly random sequence would be $e - 1$;
and our value is $e - 1 + (e/2 -\penalty1000 1)/a + O(1/a↑2)$. [{\sl Note:} The
same result holds for an ascending run, since we have $U↓n > U↓{n+1}$
if and only if $1 - U↓n < 1 - U↓{n+1}$. This would lead us to
suspect that runs in linear congruential sequences might
be slightly longer than normal, so the run test should be
applied to such generators.]

\ansno 25. $x$ must be in the interval
$[(k + α↑\prime - \theta)/a, (k + β↑\prime - \theta)/a)$ for some $k$,
and also in the interval $[α, β)$. Let $k↓0 = \lceil aα + \theta - β↑\prime \rceil$,
$k↓1 = \lceil aβ + \theta - β↑\prime \rceil$.  
With due regard to boundary
conditions, we get the probability
$$(k↓1 - k↓0)(β↑\prime - α↑\prime )/a + \max
\biglp 0,β - (k↓1 + α↑\prime - \theta)/a\bigrp - \max\biglp
0, α - (k↓0 + α↑\prime - \theta)/a\bigrp.$$
This is $(β - α)(β↑\prime - α↑\prime ) +
\epsilon $, where $|\epsilon | < 2(β↑\prime - α↑\prime )/a$.

\ansno 26. See Fig$.$ A--1; the orderings $U↓1
< U↓3 < U↓2$ and $U↓2 < U↓3 < U↓1$ are impossible; the other
four each have probability ${1\over 4}$.

\topinsert{\vskip 28mm
\inx{COPY PREP: Fig A-1 to be inserted}
\hbox par 48mm{\caption Fig.\ A--1. Permutation regions for
Fibonacci generator.}
\vskip 13mm
\inx{COPY PREP: Fig A-2 to be inserted}
\hbox par 48mm{\caption Fig.\ A--2. Run-length regions for Fibonacci
generator.}}

\ansno 27. $U↓n = \{F↓{n-1}U↓0 + F↓nU↓1\}$. We need to have both
$F↓{k-1}U↓0
+ F↓kU↓1 < 1$ and $F↓kU↓0 + F↓{k+1}U↓1 > 1$. The half-unit-square
in which $U↓0 > U↓1$ is broken up as shown in Fig$.$↔A--2, with
various values of $k$ indicated. The probability for a run of
length $k$ is↔${1\over 2}$, if $k = 1$; $1/F↓{k-1\,}F↓{k+1} - 1/F↓{k\,}F↓{k+2}$,
if $k > 1$. The corresponding probabilities for a random sequence
are $2k/(k+1)!-2(k+1)/(k+2)!$; the following table compares the
first few values.

\penalty1000\vskip 6pt\ctrline{$\baselineskip 14pt
\vcenter{\halign{#⊗\quad\ctr{$#$}⊗\quad\ctr{$#$}⊗\quad\ctr{$#$}⊗\quad
\ctr{$#$}⊗\quad\ctr{$#$}\cr
\hfill $k$: \hfill⊗1⊗2⊗3⊗4⊗5\cr
Probability in Fibonacci case:\hfill⊗1\over 2⊗1\over
3⊗1\over 10⊗ 1\over 24⊗ 1\over 65\cr
Probability in random case:\hfill⊗1\over 3⊗5\over 12⊗11\over
60⊗19\over 360⊗29\over 2520\cr}}$}

\ansno 28. Fig$.$ A--3 shows the various regions in the
general case. The ``213'' region means $U↓2 < U↓1 < U↓3$, if
$U↓1$ and $U↓2$ are chosen at random; the ``321'' region means
that $U↓3 < U↓2 < U↓1$, etc. The probabilities for 123 and 321 are
${1\over 4} - α/2 + α↑2/2$; the probabilities for all other
cases are ${1\over 8} + α/4 - α↑2/4$. To have all equal to
${1\over 6}$, we must have $1 - 6α + 6α↑2 = 0$.\xskip
[This exercise establishes a theorem due to J. N. \α{Franklin},
{\sl Math$.$ Comp$.$ \bf 17} (1963), 28--59, Theorem↔13; other results
of Franklin's paper are related to exercises 22 and↔23.]

\topinsert{\vskip 104mm
\inx{COPY PREP: Fig A-3 to be inserted}
\ctrline{\caption Fig.\ A--3. Permutation regions for a generator
with potency 2; $α = (a - 1)c/m$.}}

\ansbegin{3.3.4}

\ansno 1. $\nu ↓1$ is always $m$ and
$\mu ↓1 = 2$, for generators of maximum period.

\ansno 2. Let $V$ be the matrix whose rows are
$V↓1, \ldotss , V↓t$. To minimize $Y \cdot Y$, subject to the
condition that $Y ≠ (0, \ldotss , 0)$ and $VY$ is an integer
column vector $X$, is equivalent to minimizing $(V↑{-1}X) \cdot
(V↑{-1}X)$, subject to the condition that $X$ is a nonzero integer
column vector. The columns of $V↑{-1}$ are $U↓1$, $\ldotss$, $U↓t$.

\ansno 3. $a↑2 ≡ 2a - 1$ and $a↑3 ≡ 3a - 2 \modulo
m$. By considering all short solutions of (15), we find that
$\nu↓3↑2 = 6$ and $\nu↓4↑2 = 4$, for the respective
vectors $(1, -2, 1)$ and $(1, -1, -1, 1)$, except in the following
cases: $m = 2↑eq$, $q$ odd, $e ≥ 3$, $a ≡ 2↑{e-1} \modulo {2↑e}$,
$a ≡ 1 \modulo q$, $\nu↓3↑2 = \nu↓4↑2 = 2$; $m =
3↑eq$, $\gcd(3, q) = 1$, $e ≥ 2$, $a ≡ 1 \pm 3↑{e-1} \modulo {3↑e}$,
$a ≡ 1 \modulo q$, $\nu↓4↑2 = 2$; $m = 9$, $a = 4$ or 7,
$\nu↓2↑2 = \nu↓3↑2 = 5$.

\ansno 4. (a)\9 The unique choice for $(x↓1, x↓2)$
is ${1\over m}(y↓1u↓{22} - y↓2u↓{21}, -y↓1u↓{12} + y↓2u↓{11})$,
and this is $≡ {1\over m}(y↓1u↓{22} + y↓2au↓{22}, -y↓1u↓{12}
- y↓2au↓{12}) ≡ (0, 0) \modulo 1$; i.e., $x↓1$ and $x↓2$ are
integers.\xskip (b) When $(x↓1, x↓2) ≠ (0, 0)$, we have $(x↓1u↓{11}
+ x↓2u↓{21})↑2 + (x↓1u↓{12} + x↓2u↓{22})↑2 = x↓1↑2{(u
↓{11}↑2 + u↓{12}↑2)} + x↓2↑2(u↓{21}↑2 + u↓{22}↑2)
+ 2x↓1x↓2(u↓{11}u↓{21} + u↓{12}u↓{22})$, and by hypothesis this is $≥ (x↓1↑2
+ x↓2↑2 - |x↓1x↓2|)(u↓{11}↑2 + u↓{12}↑2)
≥ u↓{11}↑2+u↓{12}↑2$.\xskip [Note that this is a stronger
result than Lemma↔A\null, which tells us only that $x↓1↑2
≤ (u↓{11}↑2 + u↓{12}↑2)(u↓{21}↑2 + u↓{22}↑2)
/m↑2$ and that $x↓2↑2 ≤ {(u↓{11}↑2 + u↓{12}↑2)↑2/m↑2}$,
where the latter can be $≥1$. The idea is essentially \α{Gauss}'s notion
of a reduced binary quadratic form, {\sl Disq.\ Arith.\ }(Leipzig:
1801), $\section 171$.]

\ansno 5. Conditions (30) remain invariant; hence
$h$ cannot be zero in step S2, when $a$ is relatively prime
to $m$. Since $h$ always decreases in that step, S2 eventually
terminates with $u↑2 + v↑2 ≥ s$. Note that $pp↑\prime ≤ 0$ throughout
the calculation.

The hinted inequality surely holds the first time step S2 is performed.
The integer $q↑\prime$ that minimizes $(h↑\prime - qh)↑2
+ (p↑\prime - q↑\prime p)↑2$ is $q↑\prime = \hbox{round}\biglp(h↑\prime
h + p↑\prime p)/(h↑2 + p↑2)\bigrp$, by (24).
If $(h↑\prime - q↑\prime h)↑2 + (p↑\prime - q↑\prime p)↑2 <
h↑2 + p↑2$ we must have $q↑\prime ≠ 0$, $q↑\prime ≠ -1$, hence
$(p↑\prime - q↑\prime p)↑2 ≥ p↑2$, hence $(h↑\prime - q↑\prime
h)↑2 < h↑2$, i.e., $|h↑\prime - q↑\prime h| < h$, i.e., $q↑\prime$ is
$q$ or $q + 1$. We have $hu + pv ≥ h(h↑\prime - q↑\prime h)
+ p(p↑\prime - q↑\prime p) ≥ -{1\over 2}(h↑2 + p↑2)$, so if
$u↑2 + v↑2 < s$ the next iteration of step S2 will preserve
the assumption in the hint. If $u↑2 + v↑2 ≥ s > (u - h)↑2 +
(v - p)↑2$, we have $2|h(u - h) + p(v - p)| = 2\biglp h(h -
u) + p(p - v)\bigrp = (u - h)↑2 + (v - p)↑2 + h↑2
+ p↑2 - (u↑2 + v↑2) ≤ (u - h)↑2 + (v - p)↑2 ≤ h↑2 + p↑2$, hence
$(u - h)↑2 + (v - p)↑2$ is minimal by exercise↔4. Finally if
both $u↑2 + v↑2$ and $(u - h)↑2 + (v - p)↑2$ are $≥s$, let $u↑\prime
= h↑\prime - q↑\prime h$, $v↑\prime = p↑\prime - q↑\prime p$;
then $2|hu↑\prime + pv↑\prime | ≤ h↑2 + p↑2 ≤ {u↑\prime}↑2 +
{v↑\prime}↑2$, and $h↑2 + p↑2$ is minimal by exercise↔4.

\ansno 6. If $u↑2 + v↑2 ≥ s > (u - h)↑2 + (v -
p)↑2$ in the previous answer, we have $(v - p)↑2 > v↑2$, hence
$(u - h)↑2 < u↑2$; and if $q = a↓j$, so that $h↑\prime = a↓jh
+ u$, we must have $a↓{j+1} = 1$. It follows that $\nu
↓2↑2 = \min↓{0≤j<t}(m↓j↑2 + p↑{2}↓{j-1})$, in
the notation of exercise 3.3.3--16.

Now we have $m↓0 = m↓jp↓j + m↓{j+1}p↓{j-1} = a↓jm↓jp↓{j-1} + m↓jp↓{j-2}
+ m↓{j+1}p↓{j-1} < (a↓j + 1 + 1/a↓j)m↓jp↓{j-1} ≤ (A + 1 + 1/A)m↓jp↓{j-1}$,
and $m↓j↑2 + p↑{2}↓{j-1} ≥ 2m↓jp↓{j-1}$, hence the result.

\ansno 7. We shall prove, using condition (19),
that $U↓j \cdot U↓k = 0$ for all $k ≠ j$ iff $V↓j \cdot V↓k
= 0$ for all $k ≠ j$. Assume that $U↓j \cdot U↓k = 0$ for all
$k ≠ j$, and let $U↓j = α↓1V↓1 + \cdots + α↓tV↓t$. Then $U↓j
\cdot U↓k = α↓k$ for all $k$, hence $U↓j = α↓jV↓j$, and $V↓j
\cdot V↓k = α↑{-1}↓{j}(U↓j \cdot V↓k) = 0$ for all $k ≠ j$.
A symmetric argument proves the converse.

\ansno 8. Clearly $\nu↓{t+1} ≤ \nu ↓t$ (a fact used
implicitly in Algorithm↔S\null, since $s$ is not changed when $t$
increases). For $t = 2$ this is equivalent to $(m\mu ↓2/π)↑{1/2}
≥ ({3\over 4}m\mu ↓3/π)↑{1/3}$, i.e., $\mu ↓3 ≤ {4\over 3} \sqrt{m/π}\,
\mu ↑{3/2}↓{2}$. This reduces to ${4\over 3}10↑{-4}/
\sqrt{π}$ with the given parameters, but for large
$m$ and fixed $\mu ↓2$ the bound (39) is better.
% Vicinity of page 543
% folio 690 galley 2 	*
\ansno 9. Let $f(y↓1, \ldotss , y↓t) = \theta $; then
$\gcd(y↓1, \ldotss , y↓t) = 1$, so there is an integer matrix
$W$ of determinant 1 having $(w↓1, \ldotss , w↓t)$ as its first
row.\xskip (Prove the latter fact by induction on the magnitude of
the smallest nonzero entry in the row.)\xskip Now if $X = (x↓1, \ldotss
, x↓t)$ is a row vector, we have $XW = X↑\prime$ iff $X = X↑\prime
W↑{-1}$, and $W↑{-1}$ is an integer matrix of determinant 1,
hence the form $g$ defined by $WU$ satisfies $g(x↓1, \ldotss
, x↓t) = f(x↓1↑\prime , \ldotss , x↓t↑\prime )$;
furthermore $g(1, 0, \ldotss , 0) = \theta $.

Without loss of generality, assume that $f = g$.
If now $S$ is any orthogonal matrix, the matrix $US$ defines
the same form as $U$, since $(XUS)(XUS)↑T = (XU)(XU)↑T$. Choosing
$S$ so that its first column is a multiple of $V↓1$ and its
other columns are any suitable vectors, we have
$$US=\left(\vcenter{\halign{\ctr{$#$}⊗\ctr{$#$}\cr
α↓1⊗\quad α↓2\quad \ldots\quad α↓t\cr
0\cr
\vcenter{\baselineskip4pt\lineskip0pt\hbox{.}\hbox{.}\hbox{.}}⊗U↑\prime\cr
\noalign{\vskip 2pt}
0\cr}}\right)$$
for some $α↓1$, $α↓2$, $\ldotss$, $α↓t$ and some $(t - 1)
\times (t - 1)$ matrix $U↑\prime $. Hence $f(x↓1, \ldotss , x↓t)
= (α↓1x↓1 + \cdots + α↓tx↓t)↑2 + h(x↓2, \ldotss , x↓t)$. It follows
that $α↓1 = \sqrt{\theta }$ \raise 8.5pt\hbox{\:@\char'2}\! % 12pt left bracket
in fact, $α ↓j = (U↓1 \cdot U↓j)/ \sqrt{\theta }$
for $1 ≤ j ≤ t$\raise 8.5pt\hbox{\:@\char'3}, %12pt right bracket
and that $h$ is a positive definite quadratic
form defined by $U↑\prime $, where $\det U↑\prime = (\det U)/
\sqrt{\theta }$. By induction on $t$, there are integers
$(x↓2, \ldotss , x↓t)$ with $h(x↓2, \ldotss , x↓t) ≤ ({4\over
3})↑{(t-2)/2} |\det U|↑{2/(t-1)}/\theta ↑{1/(t-1)}$, and for
these integer values we can choose $x↓1$ so that $|x↓1 + (α↓2x↓2
+ \cdots + α↓tx↓t)/α↓1| ≤ {1\over 2}$, i.e., $(α↓1x↓1 + \cdots
+ α↓tx↓t)↑2 ≤ {1\over 4}\theta $. Hence $\theta ≤ f(x↓1, \ldotss
, x↓t) ≤ {1\over 4}\theta + ({4\over 3})↑{(t-2)/2} |\det U|↑{2/(t-1)}/\theta
↑{1/(t-1)}$ and the desired inequality follows immediately.

[{\sl Note:} For $t = 2$ the result is best possible. For
general $t$, Hermite's theorem implies that 
$\mu ↓t ≤ π↑{t/2}(4/3)↑{t(t-1)/4}/(t/2)!\,$.
A fundamental theorem due to \α{Minkowski} (``Every $t$-dimensional
convex set symmetric about the origin with volume $≥2↑t$ contains
a nonzero integer point'') gives $\mu ↓t ≤ 2↑t$; this is stronger
than Hermite's theorem for $t ≥ 9$. Even stronger results
are known, cf.\ (41).]

\ansno 10. Since $y↓1$ and $y↓2$ are relatively prime, we can
solve $u↓1y↓2 - u↓2y↓1 = m$; furthermore $(u↓1 + qy↓1)y↓2 -
(u↓2 + qy↓2)y↓1 = m$ for all $q$, so we can ensure that $2|u↓1y↓1
+ u↓2y↓2| ≤ y↓1↑2 + y↓2↑2$ by choosing an appropriate
integer $q$. Now $y↓2(u↓1 + au↓2) ≡ y↓2u↓1 - y↓1u↓2 ≡ 0 \modulo
m$, and $y↓2$ must be relatively prime to $m$, hence $u↓1
+ au↓2 ≡ 0$. Finally let $|u↓1y↓1 + u↓2y↓2| = αm$, $u↓1↑2
+ u↓2↑2 = βm$, $y↓1↑2 + y↓2↑2 = \gamma m$;
we have $0 ≤ α ≤ {1\over 2}\gamma $, and it remains to be shown
that $α ≤ {1\over 2}β$ and $β\gamma ≥ 1$. The identity $(u↓1y↓2
- u↓2y↓1)↑2 + (u↓1y↓1 + u↓2y↓2)↑2 = (u↓1↑2 + u
↓2↑2)(y↓1↑2 + y↓2↑2)$ implies that $1 + α↑2 =
β\gamma $. If $α > {1\over 2}β$, we have $2α\gamma > 1 + α↑2$,
i.e., $\gamma - \sqrt{\gamma ↑2 - 1} < α ≤
{1\over 2}\gamma $. But ${1\over 2}\gamma <
\sqrt{\gamma ↑2 - 1}$ implies that $\gamma ↑2 > {4\over 3}$,
a contradiction.

\ansno 11. Since $a$ is odd, $y↓1 + y↓2$ must be even. To avoid
solutions with $y↓1$ and $y↓2$ both even, let $y↓1 = x↓1 + x↓2$,
$y↓2 = x↓1 - x↓2$, and solve $x↓1↑2 + x↓2↑2 = m/
\sqrt{3} - \epsilon $, with $(x↓1, x↓2)$ relatively
prime and $x↓1$ even; the corresponding multiplier $a$ will
be the solution to $(x↓2 - x↓1)a ≡ x↓2 + x↓1 \modulo {2↑e}$.
It is not difficult to prove that $a ≡ 1 \modulo {2↑{k+1}}$
iff $x↓1 ≡ 0 \modulo {2↑k}$, so we get the best potency when
$x↓1 \mod 4 = 2$. The problem reduces to finding relatively prime
solutions to $x↓1↑2 + x↓2↑2 = N$ where $N$ is
a large integer of the form $4k + 1$. By factoring $N$ over
the Gaussian integers, we can see that solutions exist if and
only if each prime factor of $N$ (over the usual integers) has
the form $4k + 1$.

According to a famous theorem of \α{Fermat,} every
prime $p$ of the form $4k + 1$ can be written $p = u↑2 + v↑2
= (u + iv)(u - iv)$, $v$ even, in a unique way except for the
signs of $u$ and $v$. The numbers $u$ and $v$ can be calculated
efficiently by solving $x↑2 ≡ -1 \modulo p$, then calculating
$u + iv = \gcd(x + i, p)$ by \α{Euclid's algorithm} over the \α{Gaussian
integers}.\xskip[We can take $x = n↑{(p-1)/4} \mod p$ for almost
half of all integers↔$n$. This application of a Euclidean algorithm
is essentially the same as finding the least nonzero $u↑2 +
v↑2$ such that $u \pm xv ≡ 0 \modulo p$.]\xskip If the prime factorization
of $N$ is $p↑{e↓1}↓{1} \ldotss p↑{e↓r}↓{r} = (u↓1 + iv↓1)↑{e↓1}
(u↓1 - iv↓1)↑{e↓1} \ldotss (u↓r + iv↓r)↑{e↓r}(u↓r
- iv↓r)↑{e↓r}$, we get $2↑{r-1}$ distinct solutions to
$x↓1↑2 + x↓2↑2 = N$, $\gcd(x↓1, x↓2) = 1$, $x↓1$
even, by letting $|x↓2| + i|x↓1| = (u↓1 + iv↓1)↑{e↓1}(u↓2
\pm iv↓2)↑{e↓2}\ldotss(u↓r \pm iv↓r)↑{e↓r}$; and all
such solutions are obtained in this way.

{\sl Note:} When $m = 10↑e$, a similar procedure
can be used, but it is five times as much work since we must
keep trying until finding a solution with $x↓1 ≡ 0 \modulo
{10}$. For example, when $m = 10↑{10}$ we have $\lfloor m/
\sqrt{3}\rfloor = 5773502691$, and $5773502689 = 53 \cdot
108934013 = (7 + 2i)(7 - 2i)(2203 + 10202i)(2203 - 10202i)$.
Of the two solutions $|x↓2| + i|x↓1| = (7 + 2i)(2203 + 10202i)$
or $(7 + 2i)(2203 - 10202i)$, the former gives $|x↓1| = 67008$
(no good) and the latter gives $|x↓1| = 75820$, $|x↓2| = 4983$
(which is usable). Line 9 of Table↔1 was obtained by taking
$x↓1 = 75820$, $x↓2 = -4983$.

Line 20 of the table was obtained as follows:
$\lfloor 2↑{35}/\sqrt{3}\rfloor = 19837604196$; we drop down to 19837604193, which
is divisible by 3 so it is ineligible. Similarly, 19837604189 is divisible
by 19, and 19837604185 by 7, and 19837604181 by 3; but 19837604177
is prime and equals $131884↑2 + 49439↑2$. The corresponding multiplier
is 1175245817; a better one could be found if we continued searching.
The multiplier on line 24 is the best of the first sixteen
multipliers found by this procedure when $m=2↑{32}$.
% Vicinity of page 545
% folio 693 galley 3 	*
\ansno 12. ${U↓j}↑\prime \cdot {U↓j}↑\prime=U↓j \cdot U↓j+2\sum
↓{i≠j}q↓i(U↓i \cdot U↓j) + \sum ↓{i≠j}\sum ↓{k≠j}q↓iq↓k(U↓i \cdot
U↓k)$. The partial derivative with respect to $q↓k$ is twice
the left-hand side of (26). If the minimum can be achieved,
these partial derivatives must all vanish.

\ansno 13. $u↓{11} = 1$, $u↓{21} =$ irrational, $u↓{12} = u↓{22} = 0$.

\ansno 14. After three Euclidean steps we find $\nu↓2↑2
= 5↑2 + 5↑2$, then S4 produces
\def\\#1{\left(\vcenter{\halign{\hfill$##$\quad⊗\hfill$##$\quad⊗\hfill$##$\cr#1}}
\right)}
$$U = \\{-5⊗5⊗0\cr-18⊗-2⊗0\cr1⊗-2⊗1\cr},\qquad
V=\\{-2⊗18⊗38\cr-5⊗-5⊗-5\cr0⊗0⊗100\cr}.$$
\def\¬{\char'403} % asterisk centered on axis
Transformations $(j, q↓1, q↓2, q↓3) = (1, \¬, 0,
2)$, $(2, -4, \¬, 1)$, $(3, 0, 0, \¬)$, $(1, \¬, 0, 0)$ result in
$$U = \\{-3⊗1⊗2\cr-5⊗-8⊗-7\cr1⊗-2⊗1\cr},\qquad V=\\{-22⊗-2⊗18\cr
-5⊗-5⊗-5\cr9⊗-31⊗29\cr},\qquad Z = (0\quad0\quad1).$$
Thus $\nu ↓3 = \sqrt{6}$, as
we already knew from exercise↔3.

\ansno 15. The largest achievable $q$ in (11), minus the smallest
achievable, plus 1, is $|u↓1| + \cdots + |u↓t| - \delta $, where
$\delta = 1$ if $u↓iu↓j <
0$ for some $i$ and $j$, otherwise $\delta = 0$. For example
if $t = 5$, $u↓1 > 0$, $u↓2 > 0$, $u↓3 > 0$, $u↓4 = 0$, and $u↓5 < 0$, the largest
achievable value is $q = u↓1 + u↓2 + u↓3 - 1$ and the smallest
is $q = u↓5 + 1 = -|u↓5| + 1$.

[Note that the number of hyperplanes is unchanged
when $c$ varies, hence the same answer applies to the problem
of covering $L$ instead of $L↓0$. However, the stated formula
is {\sl not} always exact for covering $L↓0$, since the hyperplanes
that intersect the unit hypercube may not all contain points
of $L↓0$. In the example above, we can never achieve the value $q = u↓1
+ u↓2 + u↓3 - 1$ in $L↓0$ if $u↓1 + u↓2 + u↓3 > m$; it is achievable iff
there is a solution to $m - u↓1 - u↓2 - u↓3 = x↓1u↓1 + x↓2u↓2
+ x↓3u↓3 + x↓4|u↓5|$ in nonnegative integers $(x↓1, x↓2, x↓3,
x↓4)$. It may be true that the stated limits are always achievable
when $|u↓1| + \cdots +|u↓t|$ is minimal, but this does not appear
to be obvious.]

\ansno 16. It suffices to determine all solutions to (15) having
minimum $|u↓1| + \cdots +|u↓t|$, subtracting 1 if any one of
these solutions has components of opposite sign.

Instead of positive definite quadratic forms, we
work with the somewhat similar function
$f(x↓1, \ldotss , x↓t) = |x↓1U↓1 + \cdots + x↓tU↓t|$,
defining $|Y| = |y↓1| + \cdots + |y↓t|$. Inequality (21) can
be replaced by $|x↓k| ≤ (\max↓{1≤j≤t}|v↓{kj}|)\,f(y↓1,
\ldotss , y↓t)$.

Thus a workable algorithm can be obtained as follows.
Replace steps S1 through S3 by: ``Set $U ← (m)$, $V ← (1)$, $r ←
1$, $s ← m$, $t ← 1$.'' (Here $U$ and $V$ are $1 \times 1$ matrices;
thus the two-dimensional case will be handled by the general
method. A special procedure for $t = 2$ could, of course, be
devised.) In steps S4 and S8, set $s ← \min(s, |U↓k|)$. In
step S8, set $z↓k ← \lfloor \max↓{1≤j≤t}|v↓{kj}|\,s/m\rfloor$.
In step S10, set $s ← \min(s, |Y| - \delta )$; and in step
S11, output $s = N↓t$. Otherwise leave the algorithm as it stands,
since it already produces suitably short vectors.\xskip [{\sl Math.\
Comp.\ \bf 29} (1975), 827--833.]

\ansno 17. When $k > t$ in S10, and if $Y \cdot Y ≤ s$, output
$Y$ and  $-Y$; furthermore if $Y \cdot
{Y < s}$, take back the previous output of vectors for this $t$.\xskip
[In the author's experience preparing Table↔1, there was
exactly one vector (and its negative) output
for each $\nu ↓t$, except when $y↓1 = 0$ or $y↓t = 0$.]

\ansno 18. (a)\9 Let $x = m$, $y = (1 - m)/3$, $v↓{ij} = y +
x\delta ↓{ij}$, $u↓{ij} = -y + \delta ↓{ij}$. Then $V↓j \cdot
V↓k = {1\over 3}(m↑2 - 1)$ for $j ≠ k$, $V↓k \cdot V↓k = {2\over
3}(m↑2 + {1\over 2})$, $U↓j \cdot U↓j = {1\over 3}(m↑2 + 2)$, $z↓k
\approx \sqrt{2\over 9}\,m$.\xskip $\biglp$This example satisfies
(28) with $a = 1$ and works for all $m ≡ 1 \modulo 3$.$\bigrp$

(b)\9 Interchange the
r\A oles of $U$ and $V$ in step S5. Also set $s ← \min(s, U↓i
\cdot U↓i)$ for all $U↓i$ that change. For example, when $m
= 64$ this transformation with $j = 1$, applied to the matrices
of (a), reduces
$$\chop to 10pt{V = \\{43⊗-21⊗-21\cr-21⊗43⊗-21\cr-21⊗-21⊗43\cr},\quad
U=\\{22⊗21⊗21\cr21⊗22⊗21\cr21⊗21⊗22\cr}}$$
to
$$V=\\{1⊗1⊗1\cr-21⊗43⊗-21\cr-21⊗-21⊗43\cr},\quad
U=\\{22⊗21⊗21\cr-1⊗1⊗0\cr-1⊗0⊗1\cr}.$$
[Since the transformation can increase the
length of $V↓j$, an algorithm that incorporates both transformations
must be careful to avoid infinite looping. See also exercise↔23.]

\ansno 19. No, since a product of non-identity matrices with
all off-diagonal elements nonnegative and all diagonal elements↔1
cannot be the identity.

%This paragraph break introduced to fill up a sparse page (January, 1979)
[However, looping would be possible
if a subsequent transformation with $q = -1$ were performed
when $-2V↓i \cdot V↓j = V↓j \cdot V↓j$; the rounding rule must
be asymmetric with respect to sign if non-shortening transformations
are allowed.]

\ansno 20. Use the ordinary spectral test for $a$ and $m = 2↑{e-2}$;
cf.\ exercise 3.2.1.2--9.\xskip [On intuitive grounds, the same answer
should apply also when $a \mod 8 = 3$.]

\ansno 21. $X↓{4n+4} ≡ X↓{4n} \modulo 4$, so it is now appropriate
to let $V↓1 = (4, 4a↑2, 4a↑3)/m$, $V↓2 = (0, 1, 0)$, $V↓3 = (0,
0, 1)$ define the corresponding lattice $L↓0$.

\ansno 24. Let $m = p$; an analysis paralleling the text can
be given. For example, when $t = 4$ we have $X↓{n+3} = \biglp
(a↑2 + b)X↓{n+1} + abX↓n\bigrp \mod n$, and we want to minimize
$u↓1↑2 + u↓2↑2 + u↓3↑2 + u↓4↑2 ≠
0$ such that $u↓1 + bu↓3 + abu↓4≡ u↓2 + au↓3 + (a↑2 + b)u↓4
≡ 0 \modulo m$.

Replace steps S1 through S3 by the operations of
setting
$$U ← \left({m\atop 0}\quad {0\atop m}\right),\qquad V ← \left({1\quad
0\atop 0\quad 1}\right),\qquad R ← \left({1\quad 0\atop 0\quad 1}\right),\qquad
s ← m↑2,\qquad t ← 2,$$
and outputting $\nu ↓2 = m$. Replace step S4 by

\algstep S4$↑\prime$. [Advance $t$.]
If $t = T$, the algorithm terminates. Otherwise set $t ← t +
1$ and $R ← R\biglp{0\atop 1}\,{b\atop a}\bigrp\mod m$. Set $U↓t$
to the new row $(-r↓{12}, -r↓{22}, 0, \ldotss , 0, 1)$ of $t$
elements, and set $u↓{it} ← 0$ for $1 ≤ i < t$. Set $V↓t$ to
the new row $(0, \ldotss , 0, m)$. For $1 ≤ i < t$, set $q ←
\hbox{round}\biglp (v↓{i1}r↓{12} + v↓{i2}r↓{22})/m\bigrp$, $v↓{it}
← v↓{i1}r↓{12} + v↓{i2}r↓{22} - qm$, and $U↓t ← U↓t + qU↓i$.
Finally set $s ← \min(s, U↓t \cdot U↓t)$, $k ← t$, $j ← 1$.

\yskip [A similar generalization applies to all
sequences of length $p↑k-1$ defined by Eq.\ \hbox{3.2.2--8}.
Additional numerical examples
have been given by A. \α{Grube,} {\sl Zeitschrift f\"ur angewandte Math.\ und
Mechanik \bf53} (1973), T223--T225.]

\ansno 25. The given sum is at most two times the quantity $\sum↓{0≤k≤m/2d}r(dk)
=1+{1\over d}f(m/d)$, where 
$$\eqalign{\noalign{\vskip-5pt}
f(m)⊗={1\over m}\sum↓{1≤k≤m/2}\csc(πk/m)\cr
⊗={1\over m}\int↓1↑{m/2}\csc(πx/m)\,dx+O\left(1\over m\right)={1\over π}\left.\ln
\tan\left({π\over2m}x\right)\lower9pt\null\right|↓1↑{m/2}
+O\left(1\over m\right).\cr}$$ [When
$d=1$, we have $\sum↓{0≤k<m}r(k)=(2/π)\ln m+1+(2/π)\ln(2e/π)+O(1/m)$.]

\ansno 26. When $m=1$, we cannot use (52) since $k$ will be zero. If
$\gcd(q,m)=d$, the same derivation goes through with $m$ replaced by $m/d$.
Suppose we have $m=p↓1↑{e↓1}\ldotss p↓r↑{e↓r}$ and $\gcd(a-1,m)=p↓1↑{f↓1}\ldotss
p↓r↑{f↓r}$ and $d=p↓1↑{d↓1}\ldotss p↓r↑{d↓r}$. If $m$ is replaced by $m/d$,
then $s$ is replaced by
$p↓1↑{\max(0,e↓1-f↓1-d↓1)}\ldotss p↓r↑{\max(0,e↓r-f↓r-d↓r)}$.

\ansno 27. It is convenient to use the following functions:
$\rho(x)=1$ if $x=0$, $\rho(x)=x$ if $0<x≤m/2$, $\rho(x)=m-x$ if $m/2<x<m$;
$\hbox{trunc}(x)=\lfloor x/2\rfloor$ if $0≤x≤m/2$, $\hbox{trunc}(x)=m-\lfloor
(m-x)/2\rfloor$ if $m/2<x<m$;
$L(x)=0$ if $x=0$, $L(x)=\lfloor\lg x\rfloor+1$ if $0<x≤m/2$, $L(x)=-\biglp\lfloor
\lg(m-x)\rfloor+1\bigrp$ if $m/2<x<m$; and $l(x)=\max\biglp 1,2↑{|x|-1}\bigrp$.
Note that $l\biglp L(x)\bigrp≤\rho(x)<2l\biglp L(x)\bigrp$ and
$\rho(x)≤m\sin(πx/m)<π\rho(x)$ for $0<x<m$.

Say that a vector $(u↓1,\ldotss,u↓t)$ is {\sl bad} if it is nonzero and satisfies
(15); and let $\rho↓{\max}$ be the maximum value of $\rho(u↓1)\ldotsm\rho(u↓t)$
over all bad $(u↓1,\ldotss,u↓t)$.
The vector
$(u↓1,\ldotss,u↓t)$ is said to be in class $\biglp L(u↓1),\ldotss,L(u↓t)\bigrp$.
Thus there are at most $(2\lg m+1)↑t$ classes, and class $(L↓1,\ldotss,L↓t)$
contains at most $l(L↓1)\ldotsm l(L↓t)$ vectors. Our proof is based on showing that
the bad vectors in each fixed class contribute only $O(1/\rho↓{\max})$
to $\sum r(u↓1,\ldotss,r↓t)$; this proves even more than was asked, since
$1/\rho↓{\max}≤π↑t r↓{\max}$.

Let $\mu=\lfloor\lg\rho↓{\max}\rfloor$. The {\sl $\mu$-fold truncation operator}
on a vector is defined to be the following operation repeated $\mu$ times: ``Let
$j$ be minimal such that $\rho(u↓j)>1$, and replace $u↓j$ by $\hbox{trunc}(u↓j)$;
but do nothing if $\rho(u↓j)=1$ for all $j$.'' $\biglp$This
operation essentially throws away one bit of
information about $(u↓1,\ldotss,u↓t)$.$\bigrp$
If $(u↓1↑\prime,\ldotss,u↓t↑\prime)$ and $(u↓1↑{\prime\prime},\ldotss,
u↓t↑{\prime\prime})$ are two vectors of the same class having the same $\mu$-fold
truncation, we say they are {\sl similar}\/; in this case it follows that
$\rho(u↓1↑\prime-u↓1↑{\prime\prime})\ldotsm\rho(u↓t↑\prime-u↓t↑{\prime\prime})<
2↑\mu≤\rho↓{\max}$. For example, any two vectors of the form $\biglp
(1x↓2x↓1)↓2,0,m-(1x↓3)↓2,(101x↓5x↓4)↓2,(1101)↓2\bigrp$ are similar when $m$
is large and $\mu=5$; the $\mu$-fold truncation operator successively removes
$x↓1$, $x↓2$, $x↓3$, $x↓4$, $x↓5$. Since the difference of two bad vectors
satisfies (15), it is impossible for two unequal bad vectors to be similar.
Therefore class $(L↓1,\ldotss,L↓t)$ can contain at most $\max\biglp 1,
l(L↓1)\ldotsm l(L↓t)/2↑\mu\bigrp$ bad vectors.
If class $(L↓1,\ldotss,L↓t)$ contains exactly one bad vector $(u↓1,\ldotss,u↓t)$,
we have $r(u↓1,\ldotss,u↓t)≤r↓{\max}≤1/\rho↓{\max}$; if it
contains $≤l(L↓1)\ldotsm l(L↓t)/2↑\mu$ bad vectors, each of them has
$r(u↓1,\ldotss,u↓t)≤1/\rho(u↓1)\ldotsm\rho(u↓t)≤1/l(L↓1)\ldotsm l(L↓t)$.

\def\\{{\:a[}}\def\¬{{\:a]}}
\ansno 28. Let $\zeta=e↑{2πi/(m-1)}$ and let $S↓{kl}=\sum↓{0≤j<m-1}\omega
↑{x↓{j+l}}\zeta↑{jk}$. The analog of (51) is $|S↓{k0}|=\sqrt m$, hence the
analog of (53) is $\hbox{\:u\char'152}N↑{-1}\sum↓{0≤n<N}\omega↑{x↓n}
\hbox{\:u\char'152}=O\biglp(\sqrt m\log m)/N\bigrp$. The analogous theorem
now states that
$$D↓N↑{(t)}=O\left(\sqrt m(\log m)↑{t+1}\over N\right)+O\left((\log m)↑t\,r↓{\max}
\right),\qquad D↓{m-1}↑{(t)}=O\left((\log m)↑t\,r↓{\max}\right).$$
In fact, $D↓{m-1}↑{(t)}≤{m-2\over m-1}\sum r(u↓1,\ldotss,u↓t)\;$\\summed
over nonzero solutions of (15)\¬$\null+{1\over m-1}\hskip-1.4pt
\sum r(u↓1,\ldotss,u↓t)\;
$\\summed over all nonzero $(u↓1,\ldotss,u↓t)$\¬.
The latter sum is $O(\log m)↑t$ by exercise↔25 with $d=1$, and the former sum
is treated as in exercise↔27.

Let us now consider the quantity
$R(a)=\sum r(u↓1,\ldotss,u↓t)$ summed over nonzero solutions of (15). Since
$m$ is prime, each $(u↓1,\ldotss,u↓t)$ can be a solution to (15) for at most
$t-1$ values of $a$, hence $\sum↓{0<a<m}R(a)≤(t-1)\sum r(u↓1,\ldotss,u↓t)=
O\biglp t(\log m)↑t\bigrp$. It follows that the average value of $R(a)$ taken
over all $\varphi(m-1)$ primitive roots is $O\biglp t(\log m)↑t/\varphi({m-1})\bigrp$.

{\sl Note:} In general $1/\varphi(n)=O(\log\log n/n)$;
\inx{Euler phi function}
we have therefore proved that {\sl for all
prime↔$m$ and for all $T$ there exists a primitive root $a$ modulo $m$ such
that the linear congru\-en\-tial se\-quence $(1,a,0,m)$ has discrepancy $D↓{m-1}
↑{(t)}=O\biglp m↑{-1}T(\log m)↑T\log\log m\bigrp$ for ${1≤t≤T}$.} This method
of proof does {\sl not} extend to a similar result for linear congruential
generators of period $2↑e$ modulo $2↑e$, since for example the vector
$(1,-3,3,-1)$ solves (15) for about $2↑{2e/3}$ values of $a$.

\ansno 29. $u↓1↑2+\cdots+u↓t↑2≥\nu↓t↑2≥2(t-1)$ implies that $\rho(u↓1)\ldotsm
\rho(u↓t)≥\sqrt{\nu↓t↑2-(t-1)}≥\nu↓t/\sqrt2$, in the notation of exercise↔27.

\ansno 30. We wish to minimize $q|aq-mp|$ for $1≤q<m$ and $0≤p<a$. In the
notation of exercise 4.5.3--42, we have $aq↓n-mp↓n=(-1)↑nQ↓{s-n-1}(a↓{n+2},\ldotss,
a↓s)$ for ${0≤n≤s}$.\linebreak
In the range $q↓{n-1}≤q<q↓n$ we have $|aq-mp|≥|aq↓{n-1}-
mp↓{n-1}|$; consequently\linebreak
 $q|{aq-mp}|\!≥\!q↓{n-1}|aq↓{n-1}-mp↓{n-1}|$, and the minimum is
$\min↓{0≤n<s} q↓n|aq↓n-mp↓n|=\linebreak
\min↓{0≤n<s}Q↓n(a↓1,\ldotss,a↓n)
Q↓{s-n-1}(a↓{n+2},\ldotss,a↓s)$. By exercise 4.5.3--32 we have $m=
Q↓n(a↓1,\ldotss,a↓n)a↓{n+1}Q↓{s-n-1}(a↓{n+2},\ldotss,a↓s)
+Q↓n(a↓1,\ldotss,a↓n)Q↓{s-n-2}(a↓{n+3},\ldotss,a↓s)
+Q↓{n-1}(a↓1,\ldotss,a↓{n-1})Q↓{s-n-1}(a↓{n+2},\ldotss,a↓s)
$; and our problem is essentially that of maximizing the quantity
$m/Q↓n(a↓1,\ldotss,a↓n)Q↓{s-n-1}(n+2,\ldotss,a↓s)
$, which lies between $a↓{n+1}$ and $a↓{n+1}+2$.

\ansno 31. Equivalently, the conjecture is that all large $m$ can be written
$m=Q↓n(a↓1,\ldotss,a↓n)$ for some $n$ and some $a↓i\in\{1,2,3\}$. For fixed
$n$ the $3↑n$ numbers $Q↓n(a↓1,\ldotss,a↓n)$ have an average value of order
$(1+\sqrt2\,)↑n$, and their standard deviation is of order $(2.51527)↑n$; so
the conjecture is almost surely true. S. K. \α{Zaremba} conjectured in 1972
that all $m$ can be represented with $a↓i≤5$; T. W. \α{Cusick} made some
progress on this problem in {\sl Mathematika \bf24} (1977), 166--172. It
appears that only the cases $m=54$ and $m=150$ require $a↓i=5$, and the
largest $m$'s that require 4's are 2052, 2370, 5052, and 6234; at least, the
author has found representations with $a↓i≤3$ for all other integers less
than 2000000. When we require $a↓i≤2$, the average of $Q↓n(a↓1,\ldotss,a↓n)$
is ${4\over5}\,2↑n+{1\over5}(-2)↑{-n}$, while the standard deviation grows
as $(2.04033)↑n$. The density of such numbers in the author's experiments
(which considered $2↑6$ blocks of $2↑{14}$ numbers each, for $m≤2↑{20}$)
appears to vary between .50 and .65.

[See I. \α{Borosh} and H.
\α{Niederreiter}, to appear, for a computational method that finds multipliers
with small partial quotients. They have found 2-bounded solutions with
${m=2↑e}$ for $25≤e≤35$.]
% Vicinity of page 548
% folio 701 galley 4 	*
\ansbegin{3.4.1}

\ansno 1. $α + (β - α)U$.

\ansno 2. Let $U = X/m$; $\lfloor kU\rfloor = r$
iff $r ≤ kX/m < r + 1$ iff $mr/k ≤ X < m(r +
1)/k$ iff $\lceil mr/k\rceil ≤ X < \lceil m(r + 1)/k\rceil$.
The exact probability is given by the formula
$(1/m)\biglp\lceil m(r + 1)/k\rceil -
\lceil mr/k\rceil \bigrp = 1/k + \epsilon$, where $|\epsilon | < 1/m$.

\ansno 3. If full-word random numbers are given,
the result will be sufficiently random as in exercise↔2. But
if a linear congruential sequence is used, $k$ must be relatively
prime to the modulus $m$, lest the numbers have a very short
period, by the results of Section 3.2.1.1. For example,
if $k = 2$ and $m$ is even, the numbers will at
best be alternately 0 and 1.
The method is slower than (1) in nearly every case, so it is
not recommended.

\ansno 4. $\max(X↓1, X↓2) ≤ x$ if and only if $X↓1
≤ x$ and $X↓2 ≤ x$; $\min(X↓1, X↓2) ≥ x$ if and only if $X↓1
≥ x$ and $X↓2 ≥ x$. The probability that two independent events
both happen is the product of the individual probabilities.

\ansno 5. Obtain independent uniform deviates $U↓1$, $U↓2$.
Set $X ← U↓2$. If $U↓1 ≥ p$, set $X ← \max(X, U↓3)$, where
$U↓3$ is a third uniform deviate. If $U↓1 ≥ p + q$, also set
$X ← \max(X, U↓4)$, where $U↓4$ is a fourth uniform deviate.
This method can obviously be generalized to any polynomial,
and indeed even to infinite power series (as shown for example
in Algorithm↔S\null, which uses minimization instead of maximization).

We could also proceed as follows (suggested
by M. D. \α{MacLaren}): If $U↓1 < p$, set $X ← U↓1/p$; otherwise
if $U↓1 < p + q$, set $X ← \max\biglp (U↓1 - p)/q, U↓2\bigrp
$; otherwise set $X ← \max\biglp (U↓1 - p - q)/r, U↓2, U↓3\bigrp
$. This method requires less time than the other to obtain the
uniform deviates, although it involves further arithmetical
operations and it is slightly less stable numerically.

\ansno 6. $F(x) = A↓1/(A↓1 + A↓2)$, where $A↓1$
and $A↓2$ are the areas in Fig$.$↔A--4; so
$$F(x) = {\int ↑{x}↓0 \sqrt{1 -
y↑2}\,dy\over\int ↑{1}↓{0}\sqrt{1 - y↑2}\, dy}
= {2\over π} \mathop{\hbox{arcsin}} x + {2\over π} x \sqrt{1
- x↑2}.$$
The probability of termination at step 2 is $p
= π/4$, each time step 2 is encountered, so the number of executions
of step 2 has the \α{geometric distribution}. The characteristics
of this number are $\biglp$min 1, ave $4/π$, max $∞$, dev $(4/π)
\sqrt{1 - π/4}\bigrp$, by exercise↔17.

\topinsert{\vbox to 42mm{\vfill\baselineskip11pt
\inx{COPY PREP: Fig A-4 to be inserted}
\hbox par 50mm{\caption Fig.\ A--4. Region of ``acceptance'' for the
algorithm of exercise↔6.}}}

\ansno 7. If $k=1$, then $n↓1=n$ and the problem is trivial. Otherwise
it is always possible to find $i≠j$ such that $n↓i≤n≤n↓j$. Fill $B↓i$
with $n↓i$ cubes of color $C↓i$ and $n-n↓i$ of color $C↓j$,
then decrease $n↓j$ by $n-n↓i$ and eliminate color $C↓i$. We are
left with the same sort of problem but with $k$ reduced by 1; by
induction, it's possible.

The following algorithm can be used to compute the $P$ and $Y$ tables: Form
a list of pairs $(p↓1,1)\ldotsm(p↓k,k)$ and sort it by first components,
obtaining a list $(q↓1,a↓1)\ldotsm(q↓k,a↓k)$ where $q↓1≤\cdots≤q↓k$ and $n=k$.
Repeat the following operation until $n=0$: Set $P[a↓1-1]←kq↓1$ and
$Y[a↓1-1]←x↓{a↓n}$. Delete $(q↓1,a↓1)$ and $(q↓n,a↓n)$, then insert the
new entry $\biglp q↓n-(1/k-q↓1),a↓n\bigrp$ into its proper place in the list
and decrease $n$ by 1.

(If $p↓j≤1/k$ the algorithm will never put $x↓j$ in
the $Y$ table; this fact is used implicitly in Algorithm↔M\null.
The algorithm attempts to maximize the probability that $V<P↓K$ in (3),
by always robbing from the richest remaining element and giving it to the
poorest. However, it is very difficult to determine the absolute minimum of
this probability, since such a task is at least as difficult as the ``\α{bin-packing
\inx{NP complete problem}
problem}''; cf.\ Chapter↔7.)

\ansno 8. Replace $P↓j$ by $(j+P↓j)/k$ for $0≤j<k$.

\ansno 9. Consider the sign of $f↑{\prime\prime}(x) = 
\sqrt{2/π}\,(x↑2 - 1)e↑{-x↑2/2}$.

\ansno 10. Let $S↓j=(j-1)/5$ for $1≤j≤16$ and $p↓{j+15}=F(S↓{j+1})-
F(S↓j)-p↓j$ for $1≤j≤15$; also let $p↓{31}=1-F(3)$ and $p↓{32}=0$.
$\biglp$Eq.\ (15) defines $p↓1$, $\ldotss$, $p↓{15}$.$\bigrp$
The algorithm of exercise↔7 can now be used with $k=32$ to compute
$P↓j$ and $Y↓j$, after which we will have $1≤Y↓j≤15$ for $1≤j≤32$. Set
$P↓0←P↓{32}$ (which is 0) and $Y↓0←Y↓{32}$. Then set $Z↓j←1/(5-5P↓j)$ and
$Y↓j←{1\over5}Y↓j-Z↓j$ for $0≤j<32$; $Q↓j←1/(5P↓j)$ for $1≤j≤15$.

Let $h={1\over5}$ and $f↓{j+15}(x)=\sqrt{2/π}\,\vcenter{\hbox{\:@\char0}}
e↑{-x↑2/2}-e↑{-j↑2/50}\vcenter{\hbox{\:@\char1}}
/p↓{j+15}$
for $S↓j≤x≤S↓j+h$. Then let $a↓j=f↓{j+15}(S↓j)$ for $1≤j≤5$, $b↓j=f↓{j+15}(S↓j)$
for $6≤j≤15$; also $b↓j=-hf↑\prime↓{j+15}(S↓j+h)$ for $1≤j≤5$,
and $a↓j=f↓{j+15}(x↓j)+(x↓j-S↓j)b↓j/h$ for $6≤j≤15$, where $x↓j$ is the root
of the equation $f↓{\!j+15}↑\prime(x↓j)=-b↓j/h$. Finally set $D↓{j+15}←a↓j/b↓j$ for
$1≤j≤15$ and $E↓{j+15}←25/j$ for $1≤j≤5$, $E↓{j+15}←1/(e↑{(2j-1)/50}-1)$
for $6≤j≤15$.

Table↔1 was computed while making use of the following intermediate values:
$(p↓1,\ldotss,p↓{31})=(.156$, .147, .133, .116, .097, .078, .060, .044, .032,
.022, .014, .009, .005, .003, .002, .002, .005, .007, .009, .010, .009, .009,
.008, .006, .005, .004, .002, .002, .001, .001, .003); $(x↓6,\ldotss,x↓{15})
=(1.115$, 1.304, 1.502, 1.700, 1.899, 2.099, 2.298, 2.497, 2.697, 2.896);
$(a↓1,\ldotss,a↓{15})=(7.5$, 9.1, 9.5, 9.8, 9.9, 10.0, 10.0, 10.1, 10.1, 10.1,
10.1, 10.2, 10.2, 10.2, 10.2); $b↓1,\ldotss,b↓{15})=(14.9$, 11.7, 10.9, 10.4,
10.1, 10.1, 10.2, 10.3, 10.4, 10.5, 10.6, 10.7, 10.7, 10.8, 10.9).

\ansno 11. Let $g(t) = e↑{9/2}te↑{-t↑2/2}$ for $t
≥ 3$. Since $G(x) = \int ↑{x}↓{0} g(t)\,dt = 1 - e↑{-(x↑2-9)/2}
$, a random variable $X$ with density $g$ can be computed
by setting $X ← G↑{-1}(1 - V) = \sqrt{9 -
2 \ln V}$. Now $e↑{-t↑2/2} ≤ (t/3)e↑{-t↑2/2}$
for $t ≥ 3$, so we obtain a valid rejection method if we accept
$X$ with probability $f(X)/cg(X) = 3/X$.

\ansno 12. We have $f↑\prime (x) = xf(x) - 1 < 0$ for $x ≥ 0$,
since $f(x) = x↑{-1} - e↑{x↑2\!/2} \int ↑{∞}↓{x}\!e↑{-t↑2\!/2}\,dt/t↑2$
for $x > 0$. Let $x = a↓{j-1}$ and $y↑2 = x↑2
+ 2 \ln 2$; then $$\textstyle\sqrt{2/π} \int ↑{∞}↓{y}
e↑{-t↑2/2}\,dt = {1\over 2}\sqrt{2/π}
\,e↑{-x↑2/2}f(y) < {1\over 2}\sqrt{2/π}
\,e↑{-x↑2/2}f(x) =\dispstyle 2↑{-j},$$ hence $y > a↓j$.

\ansno 13. Take $b↓j = \mu ↓j$; consider now the problem with
$\mu ↓j = 0$ for each $j$. In matrix notation, if $Y = AX$,
where $A = (a↓{ij})$, we need $AA↑T = C = (c↓{ij})$.\xskip$\biglp$In other
notation, if $Y↓j = \sum a↓{jk}X↓k$, then the average value
of $Y↓iY↓j$ is $\sum a↓{ik}a↓{jk}$.$\bigrp$\xskip If this matrix equation
can be solved for $A$, it can be solved when $A$ is triangular,
since $A = BU$ for some orthogonal matrix $U$ and some triangular
$B$, and $BB↑T = C$. The desired triangular solution can be
obtained by solving the equations $a↓{11}↑2 = c↓{11}$,
$a↓{11}a↓{21} = c↓{12}$, $a↓{21}↑2+a↓{22}↑2= c↓{22}$,
$a↓{11}a↓{31} = c↓{13}$, $a↓{21}a↓{31} + a↓{22}a↓{32} = c↓{23}$,
$\ldotss $, successively for $a↓{11}$, $a↓{21}$, $a↓{22}$, $a↓{31}$,
$a↓{32}$, etc.\xskip [{\sl Note:} The covariance matrix must
be \α{positive semidefinite}, since the average value of $\biglp\sum y↓jY↓j\bigrp↑2$
is $\sum c↓{ij}y↓iy↓j$, which must be nonnegative. And there
is always a solution when $C$ is positive semidefinite, since
$C = U↑{-1}\hbox{diag}(λ↓1, \ldotss , λ↓n)U$, where the eigenvalues
$λ↓j$ are nonnegative, and $U↑{-1}\hbox{diag}(\sqrt{λ↓1},
\ldotss ,\sqrt{λ↓n})U$ is a solution.]

\ansno 14. $F(x/c)$ if $c > 0$, a step function if $c = 0$,
and $1 - F(x/c)$ if $c < 0$.

\ansno 15. Distribution $\int ↑{∞}↓{-∞} F↓1(x - t)\,dF↓2(t)$.
Density $\int ↑{∞}↓{-∞} f↓1(x - t)f↓2(t)\,dt$. This is called
the {\sl \α{convolution}} of the given distributions.
% Vicinity of page 551
% folio 707 galley 5 	*
\ansno 16. It is clear that $f(t) ≤ cg(t)$ for all $t$ as required.
Since $\int ↑{∞}↓{0} g(t)\,dt = 1$ we have $g(t) = Ct↑{a-1}$ for
$0 ≤ t < 1$, $Ce↑{-t}$ for $t ≥ 1$, where $C = ae/(a + e)$. A
random variable with density $g$ is easy to obtain as a mixture
of two distributions, $G↓1(x) = x↑{a}$ for $0 ≤ x < 1$, and
$G↓2(x) = 1 - e↑{1-x}$ for $x ≥ 1$:

\yyskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf G1. }\!
[Initialize.]\xskip Set $p ← e/(a + e)$.\xskip
(This is the probability that $G↓1$ should be used.)

\yskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf G2. }\!
[Generate $G$ deviate.]\xskip Generate
independent uniform deviates $U$, $V$, where $V ≠ 0$. If $U <
p$, set $X ← V↑{1/a}$ and $q ← e↑{-X}$; otherwise set $X ← 1
- \ln V$ and $q ← X↑{a-1}$.\xskip (Now $X$ has density $g$, and $q
= f(X)/cg(X)$.)

\yskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf G3. }\!
[Reject?]\xskip Generate a
new uniform deviate $U$. If $U ≥ q$, return to G2.\quad\blackslug

\yyskip\noindent The average number of iterations
is $c = (a + e)/\biglp e\,\Gamma (a + 1)\bigrp < 1.4$.

It is possible to streamline this procedure in
several ways. First, we can replace $V$ by an exponential deviate
$Y$ of mean 1, generated by Algorithm↔S\null, say, and then we set
$X ← e↑{-Y/a}$ or $X ← 1 + Y$ in the two cases. Moreover, if
we set $q ← pe↑{-X}$ in the first case and $q ← p + (1 - p)X↑{a-1}$
in the second, we can use the original $U$ instead of a newly
generated one in step G3. Finally if $U < p/e$ we can accept
$V↑{1/a}$ immediately, avoiding the calculation of $q$ about
30 percent of the time.

\ansno 17. (a)\9 $F(x) = 1 - (1 - p)↑{\lfloor x \rfloor}$, for $x ≥ 0$.\xskip
(b) $G(z) = pz/\biglp 1 - (1 - p)z\bigrp$.\xskip (c) Mean $1/p$,
standard deviation $\sqrt{1-p}/p$. To do the
latter calculation, observe that if $H(z) = q + (1 - q)z$, then
$H↑\prime (1) = 1 - q$ and $H↑{\prime\prime} (1) + H↑\prime (1) - \biglp
H↑\prime (1)\bigrp ↑2 = q(1 - q)$, so the mean and variance
of $1/H(z)$ are $q - 1$ and $q(q - 1)$, respectively.\xskip (See Section
1.2.10.)\xskip In this case, $q = 1/p$; the extra factor $z$ in the
numerator of $G(z)$ increases the mean by one.

\ansno 18. Set $N ← N↓1 + N↓2 - 1$, where $N↓1$ and $N↓2$
independently have the geometric distribution for probability
$p$.\xskip (Consider the generating function.)

\ansno 19. Set $N ← N↓1 + \cdots + N↓t - t$, where the $N↓j$
have the geometric distribution for $p$.\xskip (This is the number
of failures before the $t$th success, when a sequence of independent
trials are made each of which succeeds with probability $p$.)

For $t = p = {1\over 2}$, and in general when
the mean value $\biglp$namely $t(1 - p)/p\bigrp$
of the distribution is small, we can simply evaluate the probabilities
$p↓n = {t - 1 + n\choose n}p↑t(1 - p)↑n$ consecutively for $n
= 0$, 1, 2, $\ldots$ as in the following algorithm:

\yyskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf B1. }\!
[Initialize.]\xskip Set $N ← 0$, $q ← p↑t$,
$r ← q$, and generate a random uniform deviate $U$.\xskip (We will
have $q = p↓N$ and $r = p↓0 + \cdots + p↓N$ during this algorithm,
which stops as soon as $U < r$.)

\yskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf B2. }\!
[Search.] If $U ≥ r$, set $N
← N + 1$, $q ← q(1 - p)(t - 1 + N)/N$, $r ← r + q$, and repeat this
step.\quad\blackslug

\yyskip [An interesting technique
for the negative binomial distribution, for arbitrarily large
real values of $t$, has been suggested by R. \α{L\'eger}:
First generate a random gamma deviate $X$ of order $t$, then let
$N$ be a random Poisson deviate of mean $X(1 - p)/p$.]

\ansno 20. $\hbox{R1}=1+(1-A/R)\cdot\hbox{R1}$. When R2 is performed,
the algorithm terminates with probability $I/R$; when R3 is performed,
it goes to R1 with probability $E/R$. We have
$$\vbox{\halign{#\qquad⊗\ctr{$#$}\qquad⊗\ctr{$#$}\qquad⊗\ctr{$#$}\qquad
⊗\ctr{$#$}\cr
R1⊗R/A⊗R/A⊗R/A⊗R/A\cr
R2⊗0⊗R/A⊗0⊗R/A\cr
R3⊗0⊗0⊗R/A⊗R/A-I/A\cr
R4⊗R/A⊗R/A-I/A⊗R/A-E/A⊗R/A-I/A-E/A\cr}}$$

\ansno 21. $R=\sqrt{8/e}\approx 1.71153$; $A=\sqrt{π/2}\approx 1.25331$.
Since $$\int u\sqrt{a-bu}\,du=\textstyle
(a-bu)↑{3/2}\left({2\over5}(a-bu)-{2\over3}\right)
/b↑2,$$ we have $I=\int↓0↑{a/b}u\sqrt{a-bu}\,du={4\over15}a↑{5/2}/b↑2$ where $a=4(1+
\ln c)$ and $b=4c$; when $c=e↑{1/4}$, $I$ has its maximum value ${5\over6}\sqrt
{5/e}\approx1.13020$. Finally the following integration formulas are needed for
$E$:$$\eqalign{\int\sqrt{bu-au↑2}\,du⊗
\textstyle={1\over8}b↑2a↑{-3/2}\hbox{arcsin}(2ua/b-1)+
{1\over4}ba↑{-1}\sqrt{bu-au↑2}\,(2ua/b-1),\cr\noalign{\vskip 2pt}
\int\sqrt{bu+au↑2}\,du⊗\textstyle=-{1\over 8}
b↑2a↑{-3/2}\ln\vcenter{\hbox{\:@\char0}}
\sqrt{bu+au↑2}+u\sqrt a+b/2\sqrt a\vcenter{\hbox{\:@\char1}}\cr
⊗\hskip100pt \textstyle\null+{1\over4}ba↑{-1}\sqrt{bu+au↑2}\,
(2ua/b+1),\cr}$$ where $a,b>0$. Let the test in step R3 be ``$X↑2≥4e↑{x-1}/U-4x$'';
then the exterior region hits the top of the rectangle when $u=r(x)=\biglp e↑x
-\sqrt{e↑{2x}-2ex}\bigrp/2ex$.\xskip (Incidentally, $r(x)$ reaches its maximum value
at $x=1/2$, a point where it is {\sl not} differentiable!)\xskip We have $E=\int↓0
↑{r(x)}\biglp\sqrt{2/e}-\sqrt{bu-au↑2}\bigrp\,du$ where $b=4e↑{x-1}$ and
$a=4x$. The maximum value of $E$ occurs near $x=-.35$, where we
have $E\approx.29410$.

\ansno 22. (Solution by G. \α{Marsaglia}.)\xskip Consider the ``\α{continuous
Poisson distribution}'' de\-fined by $G(x) = \int ↑{∞}↓{\mu } e↑{-t}t↑{x-1}
\,dt/\Gamma (x)$, for $x > 0$; if $X$ has this distribution then
$\lfloor X\rfloor$ is Poisson distributed, since $G(x + 1) -
G(x) = e↑{-\mu}\mu↑x/x!$. If $\mu$ is large, $G$ is approximately
normal, hence $G↑{-1}\biglp F↓\mu(x)\bigrp$ is approximately linear,
where $F↓\mu(x)$ is the distribution function for a normal deviate
with mean and variance $\mu$; i.e., $F↓\mu(x)={F\biglp (x-\mu)/\sqrt\mu\bigrp}$,
where $F(x)$ is the normal distribution function (10). Let $g(x)$
be an efficiently computable function such that $|G↑{-1}\biglp
F↓\mu(x)\bigrp - g(x)| < \epsilon$ for ${-∞ < x < ∞}$; we can now
generate Poisson deviates efficiently as follows: Generate a
normal deviate↔$X$, and set $Y ← g(\mu+\sqrt\mu\,X)$, $N ← \lfloor Y\rfloor
$, $M ← \lfloor Y + {1\over 2}\rfloor $. If $|Y - M| > \epsilon
$, output↔$N$; otherwise output $M - 1$ or $M$, according as
$G↑{-1}\biglp F(X)\bigrp < M$ or not.

This approach applies also to the binomial distribution,
\inx{continuous binomial distribution}
with $$G(x) = \int ↑{1}↓{p} u↑{x-1}(1 - u)↑{n-x}\, du\,\Gamma (t
+ 1)/\Gamma (x)\Gamma (t + 1 - x),$$ since $\lfloor G↑{-1}(U)\rfloor$
is binomial with parameters $(t, p)$ and $G$ is approximately
normal.

[See also the alternative method proposed by \α{Ahrens} and \α{Dieter} in
{\sl Computing} (1980), to appear.]
% Vicinity of page 553
% folio 710 galley 6 	*
\ansno 23. Yes. The second method calculates $|\cos 2\theta
|$, where $\theta$ is uniformly distributed between 0 and $π/2$.\xskip
(Let $U = r \cos \theta$, $V = r \sin \theta$.)

\ansno 25. ${21\over 32} = (.10101)↓2$. In general,
the binary representation is formed by using 1 for↔$∨$ and 0 for↔$∧$,
from left to right, then suffixing↔1. This technique [cf.\
K. D. \α{Tocher,} {\sl J. Roy.\ Stat.\ Soc \ \bf B-16} (1954), 49]
can lead to efficient generation of independent bits having
a given probability $p$, and it can also be applied to the geometric and binomial
distributions.

\ansno 26. (a)\9 True, $\sum ↓k\Pr(N↓1 = k)\Pr(N↓2 = n - k)
= e↑{-\mu↓1-\mu↓2}(\mu↓1+\mu↓2)↑n/n!$.\xskip (b)
False, unless $\mu ↓2 = 0$; otherwise $N↓1 - N↓2$ might be
negative.

\ansno 27. Let the binary representation of $p$ be $(.b↓1b↓2b↓3
\ldotsm)↓2$, and proceed according to the following rules:

\yyskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf B1. }\!
[Initialize.]\xskip Set $m
← t$, $N ← 0$, $j ← 1$.\xskip (During this algorithm, $m$ represents the
number of simulated uniform deviates whose relation to $p$ is
still unknown, since they match $p$ in their leading $j - 1$
bits; and $N$ is the number of simulated deviates known to be
less than $p$.)

\yskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf B2. }\!
[Look at next column of bits.]\xskip
Generate a random integer $M$ with the binomial distribution
$(m, {1\over 2})$.\xskip (Now $M$ represents the number of unknown
deviates that fail to match $b↓j$.)\xskip Set $m ← m - M$, and if
$b↓j = 1$ set $N ← N + M$.

\yskip\hangindent 38pt\noindent\hbox to 38pt{\hfill\bf B3. }\!
[Done?]\xskip If $m = 0$, or if the remaining bits $(.b↓{j+1}b↓{j+2}
\ldotsm)↓2$ of $p$ are all zero, the algorithm terminates. Otherwise, set $j ← j
+ 1$ and return to step B2.\penalty1000\quad\blackslug

\yyskip\noindent [When $b↓j = 1$ for infinitely
many $j$, the average number of iterations $A↓t$ satisfies
$$\chop to 12pt{A↓0 = 0;\qquad A↓n = 1 + {1\over 2↑n} \sum ↓{k}{n\choose k}
A↓k,\quad\hbox{for }n ≥ 1.}$$
Letting $A(z) = \sum A↓nz↑n/n!$, we have $A(z)
= e↑z - 1 + A({1\over 2}z)e↑{z/2}$. Therefore $A(z)e↑{-z} = 1 -
e↑{-z} + A({1\over 2}z)e↑{-z/2} = \sum ↓{k≥0}(1 - e↑{-z/2↑k}
) = 1 - e↑{-z} - \sum ↓{n≥1}(-z)↑n/{\biglp n! (2↑n - 1)\bigrp}$,
and
$$A↓m = 1 + \sum ↓{k≥1} {n\choose k} {(-1)↑{k+1}\over
2↑k - 1} = 1 + {V↓{n+1}\over n + 1} = \lg n + {\gamma \over
\ln 2} + {1\over 2} + f↓0(n) + O(n↑{-1})$$
in the notation of exercise 5.2.2--48.]

\baselineskip 13pt %the next exercise wants loose spacing
\ansno 28. Generate a random point $(y↓1, \ldotss , y↓n)$ on
the unit sphere, and let $\rho = \sqrt{\sum
a↓ky↓k↑2}$. Generate an independent uniform deviate $U$,
and if $\rho ↑{n+1}U < K\sqrt{\sum a↓k↑2
y↓k↑2}$, output the point $(y↓1/\rho , \ldotss , y↓n/\rho )$; otherwise
start over. Here $K↑2 = \min\leftset(\sum a↓ky↓k↑2)↑{n+1}/(\sum
a↓k↑2y↓k↑2)\relv \sum y↓k↑2 = 1\rightset = a↑{n-1}↓{n}$
if $na↓n ≥ a↓1$, $\biglp(n + 1)/(a↓1 + a↓n)\bigrp↑{n+1}(a↓1a↓n/n)↑n$ otherwise.

\baselineskip 11pt % resume normal interline spacing
\ansno 29. Let $X↓{n+1}=1$, then set $X↓k←X↓{k+1}U↓{\!k}↑{1/k}$ or $X↓k←
X↓{k+1}e↑{-Y↓k/k}$
for $k=n$, $n-1$, $\ldotss$,↔1, where $U↓k$ is uniform or $Y↓k$ is exponential.\xskip
[{\sl ACM Trans.\ Math.\ Software}, to appear.]

\ansbegin{3.4.2}

\ansno 1. There are $N - t\choose n-m$
ways to pick $n - m$ records from the last $N - t$; $N-t-1\choose n-m-1$
ways to pick $n - m - 1$ from $N -
t - 1$ after selecting the $(t + 1)$st item.

\ansno 2. Step S3 will never go to step S5 when
the number of records left to be examined is equal to $n - m$.

\ansno 3. We should not confuse ``conditional''
and ``unconditional'' probabilities. The quantity $m$ depends
randomly on the selections that took place among the first
$t$ elements; if we take the average over all possible choices
that could have occurred among these elements, we will find that
$(n - m)/(N - t)$ is exactly $n/N$ on the average. For example,
consider the second element; if the first element was selected
in the sample (this happens with probability $n/N$), the second
element is selected with probability $(n - 1)/(N - 1)$; if the
first element was not selected, the second is selected with
probability $n/(N - 1)$. The overall probability of selecting
the second element is $(n/N)\biglp(n - 1)/(N - 1)\bigrp + (1 - n/N)\biglp n/(N
- 1)\bigrp = n/N$.

\ansno 4. From the algorithm,
$$p(m, t + 1) = \left(1 - {n - m\over N - t}\right)\,p(m, t) + {n -
(m - 1)\over N - t} \,p(m - 1, t).$$
The desired formula can be proved by induction
on $t$. In particular, $p(n, N) = 1$.

\ansno 5. In the notation of exercise↔4, the probability
that $t = k$ at termination is $q↓k = p(n, k) - p(n, k - 1)
= {k-1\choose n-1}/{N\choose n}$. The average is $\sum↓{0≤k≤N}
kq↓k = (N + 1)n/(n + 1)$.

\ansno 6. Similarly, $\sum↓{0≤k≤N}k(k
+ 1)q↓k = (N + 2)(N + 1)n/(n + 2)$; the variance is therefore
$(N + 1)(N - n)n/(n + 2)(n + 1)↑2$.

\ansno 7. Suppose the choice is $1 ≤ x↓1 < x↓2
< \cdots < x↓n ≤ N$. Let $x↓0 = 0$, $x↓{n+1} = N + 1$. The choice
is obtained with probability $p = \prod ↓{1≤t≤N}p↓t$,
where
$$\baselineskip 14pt\lineskip3pt
\vbox{\halign{\lft{$\dispstyle p↓t={#}$,}\qquad⊗\hbox{for }$#$\hfill\cr
N-(t-1)-n+m\over N-(t-1)⊗x↓m<t<x↓{m+1};\cr
n-m\over N-(t-1)⊗t=x↓{m+1}.\cr}}$$
The denominator of the product $p$ is $N!$; the numerator
contains the terms $N - n$, $N - n - 1$, $\ldotss$, 1 for those
$t$'s that are not $x$'s, and the terms $n$, $n - 1$, $\ldotss$,
1 for those $t$'s that {\sl are} $x$'s. Hence $p = (N - n)!n!/N!$.\xskip
{\sl Example:} $n = 3$, $N = 8$, $(x↓1, x↓2, x↓3) = (2, 3, 7)$; $p
= {5\over8} {3\over 7} {2\over 6} {4\over 5} {3\over 4} {2\over
3} {1\over 2} {1\over 1}$.

\ansno 9. The reservoir gets seven records: 1,
2, 3, 5, 9, 13, 16. The final sample consists of records 2, 5, 16.

\ansno 10. Delete step R6 and the variable $m$. Replace the $I$ table by
a table of records, initialized to the first $n$ records in step R1,
and with the new record replacing the $M$th table entry in step R4.

\ansno 11. Arguing as in Section 1.2.10, which considers the
special case $n = 1$, we see that the generating function is
$$G(z) = z↑n\left({1\over n + 1} + {n\over n + 1} z\right)\left({2\over
n + 2} + {n\over n + 2} z\right)\ldotsm\left({N - n\over N} + {n\over
N} z\right).$$
The mean is $n + \sum ↓{n<t≤N}(n/t) = n(1
+ H↓N - H↓n)$; and the variance turns out to be $n(H↓N - H↓n) - n↑2(H↑{(2)}↓{N}
- H↑{(2)}↓{n})$.

\ansno 12. (Note that $π↑{-1} = (b↓tt) \ldotsm (b↓33)(b↓22)$,
so we seek an algorithm that goes from the representation of
$π$ to that for $π↑{-1}$.)\xskip Set $b↓j ← j$ for $1 ≤ j ≤ t$. Then
for $j = 2$, 3, $\ldotss$, $t$ (in this order) interchange $b↓j\xch
b↓{a↓j}$. Finally for $j = t$, $\ldotss$, 3, 2 (in this order)
set $b↓{a↓j} ← b↓j$.\xskip $\biglp$The algorithm is based on the fact that
$(a↓tt)π↓1 = π↓1(b↓tt)$.$\bigrp$

\ansno 13. Renumbering the deck 0, 1,
$\ldotss$, $2n - 2$, we find that $s$ takes card number $x$ into card number
$(2x)\mod(2n -1)$, while $c$ takes card
$x$ into $(x + 1)\mod(2n - 1)$. We have ($c$ followed
by $s) = cs = sc↑2$. Therefore any product of $c$'s and $s$'s
can be transformed into the form $s↑ic↑k$. Also $2↑{\varphi(2n-1)}
≡ 1$ $\biglp$modulo $(2n - 1)\bigrp$; since $s↑{\varphi(2n-1)}$
and $c↑{2n-1}$ are the identity permutation, at most $(2n -
1)\varphi (2n - 1)$ arrangements are possible.\xskip (The {\sl exact}
number of different arrangements is $(2n - 1)k$, where $k$ is
the order of↔2 modulo↔$(2n - 1)$. For if $s↑k = c↑j$, then $c↑j$
fixes the card 0, so $s↑k = c↑j =\null$identity.)\xskip For further details,
see {\sl SIAM Review \bf 3} (1961), 293--297.

\ansno 14. Set $Y↓j ← j$ for $t - n < j ≤ t$. Then for $j =
t$, $t - 1$, $\ldotss$, $t - n + 1$ do the following operations: Set
$k ← \lfloor jU\rfloor + 1$. If $k > t - n$ then set $X↓j ←
Y↓k$ and $Y↓k ← Y↓j$; otherwise if $k = X↓i$ for some $i > j$
(a symbol table algorithm could be used), then set $X↓j ← Y↓i$
and $Y↓i ← Y↓j$; otherwise set $X↓j ← k$.\xskip (The idea is to let
$Y↓{t-n+1}$, $\ldotss$, $Y↓j$ represent $X↓{t-n+1}$, $\ldotss$, $X↓j$,
and if $i > j$ and $X↓i ≤ t - n$ also to let $Y↓i$ represent
$X↓{X↓i}$, in the execution of Algorithm↔P.)

\ansno 15. We may assume that $n≤{1\over2}N$, otherwise it suffices to find
the $N-n$ elements {\sl not\/} in the sample. Using a hash table of size $2n$, the
idea is to generate random numbers between 1 and $N$, storing them in the table
and discarding duplicates, until $n$ distinct numbers have been generated. The
average number of random numbers generated is $N/N+N/(N-1)+\cdots+N/(N-n+1)<2n$,
by exercise 3.3.2--10, and the average time to process each number is $O(1)$.
We want to output the results in increasing order, and this can be done as
follows: Using an ordered hash table (exercise 6.4--66) with linear probing,
the hash table will appear as if the values had been inserted in increasing order.
Thus if we use
a monotonic hash address such as $\lceil nk/N\rceil$ for the key↔$k$,
it will be a simple matter to output the keys in sorted order by making at most
two passes over the table.

\ansno 16. In most cases it will be best simply to select $n$ records one at a
time by \α{Walker}'s \α{alias} method, with probabilities proportional to their
weights, rejecting an element that occurs more than once. But if some weights are
significantly larger than others, the following algorithm will sometimes be
better [cf.\ \α{Wong} and \α{Easton}, {\sl SIAM J. Comput. \bf9} (1980),
111--113]. Begin with a ``\α{complete binary tree}'' of weights $x↓i$, where
$x↓i=x↓{2i}+x↓{2i+1}$ for $1≤i<N$ and $x↓{N+i-1}=w↓i$ for $1≤i≤N$; then do the
following operation $n$ times: ``Set $j←1$, and generate $X=Ux↓1$. If $X<x↓{2j}$,
set $j←2j$, otherwise set $X←X-x↓{2j}$ and $j←2j+1$; repeat this until $j≥N$.
Then select element $j-N+1$, set $i←\lfloor j/2\rfloor$, and while $i≥1$ set
$x↓i←x↓i-x↓j$ and $i←\lfloor i/2\rfloor$. Finally set $x↓j←0$.''
% Vicinity of page 555
% folio 715 galley 7 	*
\ansbegin{3.5}

\ansno 1. A $b$-ary sequence, yes (cf.\
exercise↔2); a $[\,0,1)$ sequence, no (since only finitely many
values are assumed by the elements).

\ansno 2. It is 1-distributed and 2-distributed,
but not 3-distributed (the binary number 111 never appears).

\ansno 3. Cf.\ exercise 3.2.2--17; repeat the sequence
there with a period of length 27.

\ansno 4. The sequence begins ${1\over 3}$, ${2\over
3}$, ${2\over 3}$, ${1\over 3}$, ${1\over 3}$, ${1\over 3}$,
${1\over 3}$, ${2\over 3}$, ${2\over 3}$, ${2\over 3}$, ${2\over
3}$, ${2\over 3}$, ${2\over 3}$, ${2\over 3}$, ${2\over 3}$,
etc. When $n = 1$, 3, 7, 15, $\ldots$ we have $\nu (n) = 1$, 1,
5, 5, $\ldots$ so that $\nu (2↑{2k-1} - 1) = \nu (2↑{2k} - 1)
= (2↑{2k} - 1)/3$; hence $\nu (n)/n$ oscillates between ${1\over
3}$ and approximately ${2\over 3}$, and no limit exists.
The probability is undefined.

[The methods of Section 4.2.4 show, however, that a numerical
value {\sl can} meaningfully be assigned to $$\Pr(U↓n < {1\over
2}) = \Pr (\hbox{leading digit of the radix-4 representation of $n +
1$ is 1}),$$ namely $\log↓4 2 = {1\over 2}$.]

\ansno 5. If $\nu ↓1(n)$, $\nu ↓2(n)$, $\nu ↓3(n)$,
$\nu ↓4(n)$ are the counts corresponding to the four probabilities,
we have $\nu ↓1(n) + \nu ↓2(n) = \nu ↓3(n) + \nu ↓4(n)$ for
all $n$. So the desired result follows by addition of limits.

\def\Pro{\mathop{\overline{\char'120\char'162}}}
\def\Pru{\mathop{\underline{\char'120\char'162}}}
\ansno 6. By exercise↔5 and induction,
$$\chop to 9pt{\Pr\biglp S↓j(n)\hbox{ for some }j,\; 1 ≤ j ≤ k\bigrp 
= \sum ↓{1≤j≤k} \Pr\biglp S↓j(n)\bigrp .}$$
As $k → ∞$, the latter is a monotone sequence bounded
by 1, so it converges; and
$$\chop to 9pt{\Pru\biglp S↓j(n)\hbox{ for some }j≥1\bigrp≥\sum↓{1≤j≤k}\Pr\biglp
S↓j(n)\bigrp}$$
for all $k$. For a counterexample to equality,
it is not hard to arrange things so that $S↓j(n)$ is always
true for {\sl some} $j$, yet $\Pr\biglp S↓j(n)\bigrp = 0$ for {\sl
all} $j$.

\ansno 7. Let $p↓i = \sum ↓{j≥1}\Pr\biglp S↓{ij}(n)\bigrp
$. The result of the preceding exercise can be generalized to
$\Pru\biglp S↓j(n)\hbox{ for some }j ≥ 1\bigrp ≥ \sum ↓{j≥1}\Pru\biglp
S↓j(n)\bigrp $, for {\sl any} disjoint statements $S↓j(n)$.
So we have $1 = \Pr\biglp S↓{ij}(n)\hbox{ for some }i, j ≥ 1\bigrp
≥ \sum ↓{i≥1}\Pru\biglp S↓{ij}(n)\hbox{ for some }j ≥ 1\bigrp
≥ \sum ↓{i≥1} p↓i = 1$, and hence $\Pru\biglp S↓{ij}(n)\hbox{ for
some }j ≥ 1\bigrp = p↓i$. Given $\epsilon > 0$, let $I$ be large
enough so that $\sum↓{1≤i≤I}p↓i ≥ 1 - \epsilon $.
Let $$\phi ↓i(N) = (\hbox{number of $n<N$ with $S↓{ij}(n)$ true for
some $j ≥ 1$}\bigrp /N.$$ Clearly $\sum ↓{1≤i≤I}
\phi ↓i(N) ≤ 1$, and for all large enough $N$ we have $\sum ↓{2≤i≤I}
\phi ↓i(N) ≥ \sum ↓{2≤i≤I}p↓i - \epsilon $; hence $\phi
↓1(N) ≤ 1 - \phi ↓2(N) - \cdots - \phi ↓I(N) ≤ 1 - p↓2 - \cdots
- p↓I + \epsilon ≤ 1 - (1 - \epsilon - p↓1) + \epsilon = p↓1
+ 2\epsilon $. This proves that $\Pro\biglp S↓{1j}(n)$ for some $j ≥ 1\bigrp
≤ p↓1 + 2\epsilon $; hence $\Pr\biglp S↓{1j}(n)$ for some $j ≥ 1\bigrp
= p↓1$, and the desired result holds for $i = 1$. By symmetry
of the hypotheses, it holds for any value of $i$.

\ansno 8. Add together the probabilities
for $j$, $j + d$, $j + 2d$, $\ldots$ in Definition E.

\ansno 9. $\limsup↓{n→∞}(a↓n+b↓n)≤\limsup↓{n→∞}a↓n+\limsup↓{n→∞}b↓n$; hence we find that
$$\chop to 9pt{\limsup↓{n→∞} \biglp (y↓{1n} - α)↑2 + \cdots + (y↓{mn}
- α)↑2\bigrp ≤ mα↑2 - 2mα↑2 + mα↑2 = 0,}$$
and this can happen only if each $(y↓{jn} - α)$ tends to zero.

\ansno 10. In the evaluation of the sum in Eq$.$ (22).

\ansno 11. $\langle U↓{2n}\rangle$ is $k$-distributed if $\langle
U↓n\rangle$ is $(2, 2k)$-distributed.

\ansno 12. Let $f(x↓1, \ldotss , x↓k) = 1$ if $u ≤ \max(x↓1,
\ldotss , x↓k) < v$; $f(x↓1, \ldotss , x↓k) = 0$ otherwise. Then
apply Theorem↔B.

\ansno 13. Let
$$\eqalign{p↓k⊗ = \Pr(U↓n \hbox{ begins a gap of length }k-1)\cr
⊗=\Pr\biglp U↓{n-1} \in [α, β),\ U↓n \notin [α, β),\ \ldotss
,\ U↓{n+k-2} \notin [α, β),\ U↓{n+k-1} \in [α,β)\bigrp\cr
⊗=p↑2(1-p)↑{k-1}.\cr}$$
% Vicinity of page 557
% folio 717 galley 8 	*
It remains to translate this into the probability that $f(n)
- f(n - 1) = k$. Let $\nu ↓k(n) = \biglp \hbox{number of $j ≤ n$ with $f(j)
- f(j - 1) = k$}\bigrp $; let $\mu ↓k(n) = ($number of $j ≤ n$
with $U↓j$ the beginning of a gap of length $k - 1)$; and let
$\mu (n)$ similarly count the number of $1 ≤ j ≤ n$ with $U↓j
\in [α, β)$. We have $\mu↓k\biglp f(n)\bigrp=\nu ↓k(n)$,
$\mu\biglp f(n)\bigrp=n$. As $n → ∞$, we must have $f(n)→∞$, hence
$$\nu ↓k(n)/n = \biglp \mu ↓k(f(n))/f(n)\bigrp \cdot \biglp
f(n)/\mu (f(n))\bigrp → p↓k/p = p(1 - p)↑{k-1}.$$
[We have only made use of the fact that the sequence is
$(k + 1)$-distributed.]

\ansno 14. Let
$$\eqalign{p↓k⊗ = \Pr(U↓n\hbox{ begins a run of length }k)\cr\noalign{\vskip3pt}
⊗=\Pr(U↓{n-1} > U↓n < \cdots < U↓{n+k-1} > U↓{n+k})\cr\noalign{\vskip3pt}
⊗= {1\over (k + 2)!}\biggglp{k+2\choose1}{k+1\choose1}-{k+2\choose1}
-{k+2\choose1}+1\bigggrp\cr\noalign{\vskip3pt}
⊗= {k\over (k + 1)!} - {k + 1\over (k + 2)!}\cr}$$
(cf.\ exercise 3.3.2--13). Now proceed as in the previous
exercise to transfer this to $\Pr\biglp f(n) - f(n - 1) = k\bigrp$.\xskip
[We have assumed only that the sequence is $(k + 2)$-distributed.]

\ansno 15. For $s, t ≥ 0$ let
$$\eqalign{p↓{st}⊗ = \Pr(X↓{n-2t-3} = X↓{n-2t-2} ≠ X↓{n-2t-1} ≠
\cdots ≠ X↓{n-1}\cr⊗\hskip 45mm\hbox{and }X↓n= \cdots = X↓{n+s} ≠ X↓{n+s+1})\cr
 ⊗=2↑{-s-2t-3};\cr}$$
for $t ≥ 0$ let $q↓t = \Pr(X↓{n-2t-2} = X↓{n-2t-1}
≠ \cdots ≠ X↓{n-1}) = 2↑{-2t-1}$. By exercise↔7, $\Pr(X↓n$
is not the beginning of a coupon set$) = \sum ↓{t≥0} q↓t = {2\over
3}$; $\Pr(X↓n$ is the beginning of coupon set of length $s + 2) =
\sum ↓{t≥0} p↓{st} = {1\over 3}\cdot2↑{-s-1}$. Now proceed
as in exercise↔13.

\ansno 16. (Solution by R. P. \α{Stanley}.)\xskip Whenever the subsequence
$S = (b - 1)$, $(b - 2)$, $\ldotss$, 1, 0, 0, 1, $\ldotss$, $(b - 2)$,
$(b - 1)$ appears, a coupon set must end at the right of $S$,
since some coupon set is completed in the first half of $S$.
We now proceed to calculate the probability that a coupon set
begins at position $n$ by manipulating the probabilities that
the last prior appearance of $S$ ends at position $n - 1$, $n
- 2$, etc., as in exercise↔15.

\ansno 18. Proceed as in the proof of Theorem↔A to calculate
$\underline{\hbox{Pr}}$ and $\overline{\hbox{Pr}}$.

\ansno 19. (Solution by T. \α{Herzog}.)\xskip Yes; e.g., the sequence
$\langle U↓{\lfloor n/2\rfloor}\rangle$ when $\langle U↓n\rangle$
satisfies R4 (or even its weaker version), cf.\ exercise↔33.

\ansno 21. $\Pr(Z↓n \in M↓1, \ldotss , Z↓{n+k-1} \in M↓k) = p(M↓1)
\ldotsm p(M↓k)$, for all $M↓1$, $\ldotss$, $M↓k \in \Mscr$.

\ansno 22. If the sequence is $k$-distributed, the limit is
zero by integration and Theorem↔B\null. Conversely, note that if
$f(x↓1, \ldotss , x↓k)$ has an absolutely convergent Fourier
series
$$f(x↓1, \ldotss , x↓k) = \sum ↓{-∞<c↓1, \ldotss , c↓k<∞} a(c↓1,
\ldotss , c↓k)\exp\biglp2πi(c↓1x↓1 + \cdots + c↓kx↓k)\bigrp ,$$
we have $\lim↓{N→∞} {1\over N} \sum ↓{0≤n<N} f(U↓n,
\ldotss , U↓{n+k-1}) = a(0, \ldotss , 0) + \epsilon ↓r$, where
$$|\epsilon ↓r| ≤ \sum ↓{|c↓1|, \ldotss , |c↓k|>r} |a(c↓1, \ldotss, c↓k)|,$$
so $\epsilon ↓r$ can be made arbitrarily small.
Hence this limit is equal to $$a(0, \ldotss , 0) = \int ↑{1}↓{0}
\cdots \int ↑{1}↓{0} f(x↓1, \ldotss , x↓k)\, dx↓1 \ldotsm dx↓k,$$ and
Eq$.$ (8) holds for all sufficiently smooth functions $f$.
The remainder of the proof shows that the function in (9) can
be approximated by smooth functions to any desired accuracy.

\ansno 23. See {\sl AMM \bf 75} (1968), 260--264.

\ansno 24. This follows immediately from exercise↔22.

\ansno 25. If the sequence is equidistributed, the denominator
in Corollary↔S approaches ${1\over 12}$, and the numerator approaches
the quantity in this exercise.

\ansno 26. See {\sl Math$.$ Comp$.$ \bf 17} (1963), 50--54.\xskip [Consider
also the following example by A. G. Waterman: Let $\langle U↓n\rangle$
be an equidistributed $[\,0, 1)$ sequence and $\langle X↓n\rangle$
an $∞$-distributed binary sequence. Let $V↓n = U↓{\lceil\sqrt n\,\rceil}$
or $1 - U↓{\lceil\sqrt n\,\rceil}$ according as $X↓n$ is 0 or 1. Then
$\langle V↓n\rangle$ is equidistributed and white, but $\Pr(V↓n
= V↓{n+1}) = {1\over 2}$. Let $W↓n = (V↓n-ε↓n)\mod 1$
where $\langle \epsilon ↓n\rangle$ is any sequence that decreases
monotonically to 0; then $\langle W↓n\rangle$ is equidistributed
and white, yet $\Pr(W↓n < W↓{n+1}) = {3\over 4}$.]

\ansno 28. Let $\langle U↓n\rangle$ be $∞$-distributed, and
consider the sequence $\langle {1\over 2}(X↓n + U↓n)\rangle $.
This is 3-distributed, using the fact that $\langle U↓n\rangle$
is $(16, 3)$-distributed.

\ansno 29. If $x = x↓1x↓2 \ldotsm x↓t$ is any binary number,
we can consider the number $\nu ↑{E}↓{x}(n)$ of times $X↓p \ldotsm
X↓{p+t-1} = x$, where $1 ≤ p ≤ n$ and $p$ is even. Similarly,
let $\nu ↑{O}↓{x}(n)$ count the number of times when $p$ is
odd. Let $\nu ↑{E}↓{x}(n) + \nu ↑{O}↓{x}(n)=\nu↓x(n)$. Now
\def\\{\char'403 }
$$\nu ↑{E}↓{0}(n) = \sum \nu ↑{E}↓{0\\\\\ldots\\}(n) \approx
\sum \nu ↑{O}↓{\\0\\\ldots\\}(n)
\approx \sum \nu ↑{E}↓{\\\\0\ldots\\}
(n) \approx \cdots \approx \sum \nu ↑{O}↓{\\\\\\\ldots0}(n)$$
where the $\nu $'s in these summations have $2k$
subscripts, $2k-1$ of which are asterisks (meaning that they are being
summed over---each sum is taken over $2↑{2k-1}$ combinations of zeros and ones),
and where ``$\approx$'' denotes
approximate equality (except for an error of at most $2k$ due
to end conditions). Therefore we find that
$$\twoline{{1\over n} 2k\nu ↑{E}↓{0}(n) = {1\over n} \left(\sum
\nu ↓{\\0\\\ldots\\}(n)+\cdots+\sum\nu↓{\\\\\\\ldots0}(n)\right)}{3pt}{
\null+{1\over n}
\chop to 9pt{\sum↓x\biglp r(x)-s(x)\bigrp\nu↓x↑E(n)}+O\left(1\over n\right),}$$
where $x = x↓1 \ldotsm x↓{2k}$ contains $r(x)$ zeros
in odd positions and $s(x)$ zeros in even positions. By $(2k)$-distribution,
the parenthesized quantity tends to $k(2↑{2k-1})/2↑{2k} = k/2$.
The re\-maining sum is clearly a maximum if $\nu ↑{E}↓{x}(n) =
\nu ↓x(n)$ when $r(x) > s(x)$, and ${\nu ↑{E}↓{x}(n) = 0}$ when
$r(x) < s(x)$. So the maximum of the right-hand side becomes
$${k\over 2} + \sum ↓{0≤s<r≤k} (r - s)\left.{k\choose r}{k\choose s}\right/
2↑{2k} = {k\over 2} + k\left.{2k-1\choose k}\right/2↑{2k}.$$
% Vicinity of page 559
% folio 720 galley 9 	*
Now $\overline{\hbox{Pr}}(X↓{2n} = 0) ≤ \limsup↓{n→∞}\nu ↑{E}↓{0}(2n)/n$,
so the proof is complete.\xskip {\sl Note:}
$$\eqalign{\noalign{\vskip 4pt}
\sum ↓{r,s}{n\choose r}{n\choose s}\max(r,s)⊗=
2n2↑{2n-2} + n{2n-1\choose n};\cr
\sum ↓{r,s}{n\choose r}{n\choose s}\min(r,s)⊗=
2n2↑{2n-2} - n{2n-1\choose n}.\cr}$$

\ansno 30. Let $f(x↓1, x↓2, \ldotss , x↓{2k}) = \hbox{sign}
(x↓1 - x↓2 + x↓3 - x↓4 + \cdots - x↓{2k})$. Construct a
directed graph with $2↑{2k}$ nodes labeled $(E; x↓1, \ldotss
, x↓{2k-1})$ and $(O; x↓1, \ldotss , x↓{2k-1})$, where each $x$
is either 0 or 1. Let there be $1 + f(x↓1, x↓2, \ldotss , x↓{2k})$
directed arcs from $(E; x↓1, \ldotss , x↓{2k-1})$ to $(O; x↓2,
\ldotss , x↓{2k})$, and $1 - f(x↓1, x↓2, \ldotss , x↓{2k})$ directed
arcs leading from $(O; x↓1, \ldotss , x↓{2k-1})$ to $(E; x↓2,
\ldotss , x↓{2k})$. We find that each node has the same number of
arcs leading into it as there are leading out; for example, $(E;
x↓1, \ldotss , x↓{2k-1})$ has ${1 - f(0, x↓1, \ldotss , x↓{2k-1})}
+ {1 - f(1, x↓1, \ldotss , x↓{2k-1})}$ leading in and $1 + f(x↓1,
\ldotss , x↓{2k-1}, 0) + 1 + f(x↓1, \ldotss , x↓{2k-1}, 1)$
leading out, and $f(x, x↓1, \ldotss , x↓{2k-1}) = -f(x↓1, \ldotss
, x↓{2k-1}, x)$. Drop all nodes that have no paths leading
either in or out, i.e., $(E; x↓1, \ldotss , x↓{2k-1})$ if $f(0,
x↓1, \ldotss , x↓{2k-1}) = +1$, or $(O; x↓1, \ldotss , x↓{2k-1})$
if $f(1, x↓1, \ldotss , x↓{2k-1}) = -1$. The resulting directed
graph is seen to be connected, since we can get from any node
to $(E; 1, 0, 1, 0, \ldotss , 1)$ and from this to any desired
node. By Theorem 2.3.4.2G\null, there is a cyclic path traversing
each arc; this path has length $2↑{2k+1}$, and we may assume
that it starts at node $(E; 0, \ldotss , 0)$. Construct a cyclic
sequence with $X↓1 = \cdots = X↓{2k-1} = 0$, and $X↓{n+2k-1}
= x↓{2k}$ if the $n$th arc of the path is from $(E; x↓1, \ldotss
, x↓{2k-1})$ to $(O; x↓2, \ldotss , x↓{2k})$ or from $(O; x↓1,
\ldotss , x↓{2k-1})$ to $(E; x↓2, \ldotss , x↓{2k})$. For example,
the graph for $k = 2$ is shown in Fig.↔A--5; the arcs of the
cyclic path are numbered from 1 to 32, and the cyclic sequence
is$$(00001000110010101001101110111110)(00001\ldotsm).$$ Note that
$\Pr(X↓{2n} = 0) = {11\over 16}$ in this sequence. The sequence
is clearly $(2k)$-distributed, since each $(2k)$-tuple $x↓1x↓2
\ldotsm x↓{2k}$ occurs $1 + f(x↓1, \ldotss , x↓{2k}) + 1 - f(x↓1,
\ldotss , x↓{2k}) =2$ times in the cycle. The fact that $\Pr(X↓{2n}
= 0)$ has the desired value comes from the fact that the maximum
value on the right-hand side in the proof of the preceding exercise
has been achieved by this construction.

\topinsert{\vskip 63mm
\inx{COPY PREP: Fig A-5 to be inserted}
\ctrline{\caption Fig.\ A--5. Directed graph for the
construction in exercise 30.}}

\ansno 31. Use Algorithm↔W with rule $\Rscr↓1$ selecting the entire sequence.\xskip
[For a generalization of this
type of nonrandom behavior in R5-sequences, see Jean \α{Ville},
{\sl \'Etude Critique de la notion de Collectif} (Paris,
1939), 55--62. Perhaps R6 is also too weak, from this standpoint.]

\ansno 32. If $\Rscr,\Rscr↑\prime$ are computable subsequence rules,
so is $\Rscr↑{\prime\prime} = \Rscr\Rscr↑\prime$ defined by the following
functions: $f↓n↑{\prime\prime}(x↓0, \ldotss , x↓{n-1}) = 1$ iff
$\Rscr$ defines the subsequence $x↓{r↓1}$, $\ldotss
$, $x↓{r↓k}$ of $x↓0$, $\ldotss$, $x↓{n-1}$, where $k ≥ 0$ and
$0 ≤ r↓1 < \cdots < r↓k < n$ and $f↓k↑\prime (x↓{r↓1},
\ldotss, x↓{r↓k}) = 1$.

Now $\langle X↓n\rangle\Rscr\Rscr↑\prime$ is $\biglp \langle
X↓n\rangle\Rscr\bigrp\Rscr↑\prime $. The result follows immediately.

\ansno 33. Given $\epsilon > 0$, find $N↓0$ such that $N > N↓0$
implies that both $|\nu ↓r(N)/N - p| < \epsilon$ and $|\nu ↓s(N)/N
- p| < \epsilon $. Then find $N↓1$ such that $N > N↓1$ implies
that $t↓N$ is $r↓M$ or↔$s↓M$ for some $M > N↓0$. Now $N > N↓1$
implies that
$$\left| {\nu ↓t(N)\over N} - p\right| = \left| {\nu ↓r(N↓r)
+ \nu ↓s(N↓s)\over N} - p\right| = \left| {\nu ↓r(N↓r) - pN↓r
+ \nu ↓s(N↓s) - pN↓s\over N↓r + N↓s}\right|<ε.$$

\ansno 34. For example, if the binary representation
of $t$ is $(1\ 0↑{b-2}\ 1\ 0↑{a↓1}\ 1\ 1\ 0↑{a↓2}\ 1\ \ldots\
1\ 0↑{a↓k})↓2$, where ``$0↑a$'' stands for a sequence of $a$
consecutive zeros, let the rule $\Rscr↓t$ accept $U↓n$ if and
only if $\lfloor bU↓{n-k}\rfloor = a↓1$, $\ldotss$, $\lfloor bU↓{n-1}\rfloor
= a↓k$.

\ansno 35. Let $a↓0 = s↓0$ and $a↓{m+1} = \max\leftset s↓k \relv 0 ≤ k
< 2↑{a↓m}\rightset$. Construct a subsequence rule that selects
element $X↓n$ if and only if $n = s↓k$ for some $k < 2↑{a↓m}$,
when $n$ is in the range $a↓m ≤ n < a↓{m+1}$. Then $\lim↓{m→∞}\nu (a↓m)/a↓m
= {1\over 2}$.

\ansno 36. Let $b$ and $k$ be arbitrary but fixed integers greater
than 1. Let $Y↓n = \lfloor bU↓n\rfloor $. An arbitrary infinite
subsequence $\langle Z↓n\rangle = \langle Y↓{s↓n}\rangle\Rscr$
determined by algorithms $\Sscr$ and $\Rscr$ (as in the proof of
Theorem↔M) corresponds in a straightforward but notationally
hopeless manner to algorithms $\Sscr↑\prime$ and $\Rscr↑\prime$ that
inspect $X↓t$, $X↓{t+1}$, $\ldotss$, $X↓{t+s}$ and/or select $X↓t$,
$X↓{t+1}$, $\ldotss$, $X↓{t+\min(k-1,s)}$ of $\langle X↓n\rangle$
if and only if $\Sscr$ and $\Rscr$ inspect and/or select $Y↓s$, where
$U↓s = (0.X↓tX↓{t+1} \ldotsm X↓{t+s})↓2$. Algorithms $\Sscr↑\prime$ and
$\Rscr↑\prime$ determine an infinite 1-distributed subsequence of
$\langle X↓n\rangle$ and in fact (as in exercise↔32) this
subsequence is $∞$-distributed so it is $(k, 1)$-distributed.
Hence we find that $\underline{\hbox{Pr}}(Z↓n = a)$ and
$\overline{\hbox{Pr}}(Z↓n=a)$ differ from $1/b$ by less than $1/2↑k$.

[The result of this exercise is true if ``R6'' is replaced
consistently by ``R4'' or ``R5''; but it is false if ``R1'' is used, since
$X↓{n\choose2}$ might be identically zero.]

\ansno 37. For $n ≥ 2$ replace $U↓{n↑2}$ by ${1\over 2}(U↓{n↑2}
+ \delta ↓n)$, where $\delta ↓n = 0$ or 1 according as the set $\{U↓{(n-1)↑2+1},
\ldotss , U↓{n↑2-1}\}$ contains an even or odd
number of elements less than ${1\over 2}$.\xskip [{\sl Advances in
Math$.$ \bf 14} (1974), 333--334.]

\ansno 39. See {\sl Acta Arithmetica \bf 21} (1972), 45--50.
The best possible value of $c$ is unknown.

\ansno 40. If every one-digit change to a random table yields
a random table, all tables are random (or none are). If we don't
allow degrees of randomness, the answer must therefore be, ``Not
always.''

% Vicinity of page 560
% folio 722 galley 10a 	*
\ansbegin{3.6}

\mixans 1. {⊗RANDI⊗STJ⊗9F⊗Store exit location.\cr
⊗⊗STA⊗8F⊗Store value of $k$.\cr
⊗⊗LDA⊗XRAND⊗$\rA ← X$.\cr
⊗⊗MUL⊗7F⊗$\rAX ← aX$.\cr
⊗⊗INCX⊗1009⊗$\rX ← (aX + c)\mod m$.\cr
⊗⊗JOV⊗*+1⊗Ensure that overflow is off.\cr
⊗⊗SLAX⊗5⊗$\rA ← (aX+c)\mod m$.\cr
⊗⊗STA⊗XRAND⊗Store $X$.\cr
⊗⊗MUL⊗8F⊗$\rA ← \lfloor kX/m\rfloor$.\cr
⊗⊗INCA⊗1⊗Add 1, so that $1 ≤ Y ≤k$.\cr
⊗9H⊗JMP⊗*⊗Return.\cr
⊗XRAND⊗CON⊗1⊗Value of $X$; $X↓0 = 1$.\cr
⊗8H⊗CON⊗0⊗Temp storage of $k$.\cr
⊗7H⊗CON⊗3141592621⊗The multiplier $a$.\quad\blackslug\cr}

\ansno 2. Putting a random number generator into a program
makes the results essentially unpredictable to the programmer.
If the behavior of the machine on each problem were known in
advance, few programs would ever be written. As \α{Turing} has said,
the actions of a computer quite often {\sl do} surprise its programmer,
especially when a program is being debugged.

So the world had better watch out.

\ansno 7. In fact, you only need the 2-bit values $\lfloor X↓n/2↑{16}\rfloor
\mod4$; see D. E. \α{Knuth}, ``De\-cipher\-ing a linear congruential encryption,''
to appear. See also J. \α{Reeds}, {\sl Cryptologia \bf1} (1977), 20--26,
{\bf3} (1979), 83--95, for solutions to related problems.
\end % be sure this comes at an opportune time!